August's Box

Longest Palindromic Subsequence

Description

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:

"bbbab"

Output:

4

One possible longest palindromic subsequence is “bbbb”.
Example 2:
Input:

"cbbd"

Output:

2

One possible longest palindromic subsequence is “bb”.

Solution

题目的意思是:

找出字符串中最长的回文子序列(可不连续),显然可以用dp来解,有以下递推公式:

dp[i][j] = max(dp[i+1][j-1]+2(s[i]==s[j]), dp[i+1][j], dp[i][j-1])
其中 dp[k][k] = 1

代码如下:

python
1
2
3
4
5
6
7
8
9
10
11
12
13
def findFrequentTreeSum(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
dp = [[1 for _ in range(len(s))] for _ in range(len(s))]
for g in xrange(1, len(s)):
for i in xrange(len(s) - g):
if s[i] == s[i + g]:
dp[i][i + g] = 2 if g == 1 else dp[i + 1][i + g - 1] + 2
dp[i][i + g] = max(dp[i][i + g], dp[i + 1][i + g])
dp[i][i + g] = max(dp[i][i + g], dp[i][i + g - 1])
return dp[0][len(s) - 1] if len(s) else 0

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int longestPalindromeSubseq(string s) {
if(s.empty()) return 0;
const int length = s.length();
vector<vector<int> > dp(length, vector<int>(length, 1));
for(int gap = 1; gap < length; ++gap) {
for(int i = 0; i + gap < length; ++i) {
if(s[i] == s[i + gap])
dp[i][i + gap] = (gap == 1 ? 2 : 2 + dp[i + 1][i + gap - 1]);
dp[i][i + gap] = max(dp[i][i + gap], dp[i + 1][i + gap]);
dp[i][i + gap] = max(dp[i][i + gap], dp[i][i + gap - 1]);
}
}
return dp[0][length - 1];
}

上面的代码还可以优化,空间复杂度为O(N^2),通过回滚数组可以把空间降低到O(N)。(参考:https://discuss.leetcode.com/topic/78625/python-o-n-space-o-n-2-time)
python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def longestPalindromeSubseq(self, s):
"""
:type s: str
:rtype: int
"""
dp = [1] * len(s)
for j in xrange(1, len(s)):
pre = dp[j]
for i in reversed(xrange(0, j)):
tmp = dp[i] # actually means result of i+1~j-1
if s[i] == s[j]:
dp[i] = 2 + pre if i + 1 <= j - 1 else 2
else:
dp[i] = max(dp[i + 1], dp[i])
pre = tmp
return dp[0]