DP-12. Longest Palindromic Subsequence

Problem

LeetCode #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:

"bbbab"
Output:
4
One possible longest palindromic subsequence is “bbbb”.
Example 2:
Input:

"cbbd"
Output:
2

Explanation

This problem can be compared to the Longest Palindromic Substring. In that problem, we should find the substring of the given string, while in this problem, we only need to find the subsequence. So, in that situation, we can use boolean array to check whether the substring from i to j is palindromic. However, in this problem, we have to save the length, as the palindromic can be discontinuous.

Similarly, dp[i][j] means the longest palindrome between the scope i to j.

Solution

Time complexity is O(n^2)
Space complexity is O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int longestPalindromeSubseq(String s) {
if (s == null || s.length() == 0) return 0;
int len = s.length();
int[][] dp = new int[len][len];
for (int i = len - 1; i >= 0; i--) {
dp[i][i] = 1;
for (int j = i + 1; j < len; j++) {
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];
}
}