516 Longest Palindromic Subsequence
1. Question
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".
2. Implementation
(1) DP
class Solution {
public int longestPalindromeSubseq(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int n = s.length();
String revS = new StringBuilder(s).reverse().toString();
int[][] LCS = new int[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
LCS[i][j] = 0;
}
else if (s.charAt(i - 1) == revS.charAt(j - 1)) {
LCS[i][j] = LCS[i - 1][j - 1] + 1;
}
else {
LCS[i][j] = Math.max(LCS[i - 1][j], LCS[i][j - 1]);
}
}
}
return LCS[n][n];
}
}
3. Time & Space Complexity
DP: 时间复杂度O(n^2), 空间复杂度O(n^2)
Last updated
Was this helpful?