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 (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] 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]
|
近期评论