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".
Approach #1: DP. [Java]
class Solution {
public int longestPalindromeSubseq(String s) {
int len = s.length();
int[][] dp = new int[len+1][len+1];
for (int l = 1; l <= len; ++l) {
for (int i = 0; i <= len - l; ++i) {
int j = i + l - 1;
if (i == j) {
dp[i][j] = 1;
continue;
} else if (s.charAt(i) == s.charAt(j))
dp[i][j] = dp[i+1][j-1] + 2;
else
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
}
}
return dp[0][len-1];
}
}
Analysis:
This problem is similar with 486. Predict the Winner.
dp[i][j] : the longest palindromic subsequence from i to j.
stage: length of substring.
for len = 1 to n:
for i = 0 to n-len:
j = i + len - 1;
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2;
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
ans : dp[0][len-1].
Approach #2: optimization. [C++]
class Solution {
public:
int longestPalindromeSubseq(string s) {
int len = s.length();
vector<int> dp0(len, 0);
vector<int> dp1(len, 0);
vector<int> dp2(len, 0);
for (int l = 1; l <= len; ++l) {
for (int i = 0; i <= len - l; ++i) {
int j = i + l - 1;
if (i == j) {
dp0[i] = 1;
continue;
} else if (s[i] == s[j]) {
dp0[i] = dp2[i+1] + 2;
} else {
dp0[i] = max(dp1[i+1], dp1[i]);
}
}
dp0.swap(dp1);
dp2.swap(dp0);
}
return dp1[0];
}
};
Reference:
http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-516-longest-palindromic-subsequence/