算法
February 10, 2019

LeetCode-Longest Palindromic Subsequence

版权声明：本文为博主原创文章，转载请注明原文出处！
写作时间：2019-02-10 11:44:52

Longest Palindromic Subsequence

题目描述

这是LeetCode的第516道题目：516. Longest Palindromic Subsequence。

Given a string s, find the longest palindromic subsequence’s length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

1
"bbbab"

Output:

1
4

One possible longest palindromic subsequence is “bbbb”.

Example 2:
Input:

1
"cbbd"

Output:

1
2

One possible longest palindromic subsequence is “bb”.

题目要求我们计算出给定字符串中的最长回文序列（这里的序列不是一定要在给定字符串中连续排列的，就是挑出的单个字符按其在给定字符串中的顺序排列以后是回文即可）

思路分析

其实，思路跟第647道题目Palindromic Substrings是类似的，可以采用动态规划进行。但是因为回文序列不是给定字符串的连续子串，貌似不能使用中心扩散法求解。

使用动态规划，我们设dp[i][j]表示从第i个字符到到j个字符回文序列的长度，则有：

  1. 当s[i] == s[j]时，dp[i][j] = dp[i+1][j-1] + 2
  2. 当s[i] != s[j]时，dp[i][j] = max(dp[i+1][j], dp[i][j-1])

C++实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        const int length = s.length();
        vector<vector<int>> dp(length, vector<int>(length));
        for (auto i = length - 1; i >= 0; --i) {
            dp[i][i] = 1;
            for (auto j = i + 1; j < length; ++j) {
                dp[i][j] = s[i] == s[j] ?
                        dp[i + 1][j - 1] + 2 :
                        max(dp[i + 1][j], dp[i][j - 1]);
            }
        }
        return dp[0][length - 1];
    }
};

Scala实现

Scala版本是对C++版本的翻译

1
2
3
4
5
6
7
8
9
10
11
12
13
14
object Solution {
  def longestPalindromeSubseq(s: String): Int = {
    val length = s.length
    val dp = Array.ofDim[Int](length, length)
    for (i <- length - 1 to 0 by -1) {
      dp(i)(i) = 1
      for (j <- i + 1 until length) {
        dp(i)(j) = if (s(i) == s(j)) dp(i + 1)(j - 1) + 2
        else math.max(dp(i + 1)(j), dp(i)(j - 1))
      }
    }
    return dp(0)(length - 1)
  }
}