leetcode解题: Longest Palindromic Subsequence (516)

发表于 | 分类于

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”

解法1：DP: O(N^2)

字符串的问题的DP有的时候需要考虑2D的DP解法。这题就是一个列子。
假设dp[i][j]是指(i,j)的子字符串的LPS, 那么如果首尾字符相同的话
dp[i][j] = dp[i + 1][j - 1] + 2
如果不相同的话，可以是错位match，也就是说要么用上尾字符，要么用上头字符。
dp[i][j] = max(dp[i+1][j], dp[i][j-1])

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int longestPalindromeSubseq(string s) {
        
        if (s.size() == 0) return 0;
        
        int n = s.size() - 1;
        
        int dp[n + 1][n + 1] {0};
        
        for (int i = 0; i <= n; ++i) {
            dp[i][i] = 1;
        }
        
        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j <= n; ++j) {
                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]);
                }
            }
        }
        
        return dp[0][n];
    }
};

Java

1