516. Longest Palindromic Subsequence

https://leetcode.com/problems/longest-palindromic-subsequence/

Problem

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".

Constraints:

• 1 <= s.length <= 1000

• s consists only of lowercase English letters.

Solution

1. Using LCS

class Solution {
public:
    int longestPalindromeSubseq(string &s) {
        string s2 = s;
        reverse(s2.begin(), s2.end());
        return LCS(s, s2);
    }
    inline int LCS(string &s1, string &s2) {
        const int m = s1.size() + 1, n = s2.size() + 1;
        int dp[m][n];
        memset(dp, 0, m * n * sizeof(int));
        for (int i = 1; i <= s1.size(); ++i) {
            for (int j = 1; j <= s2.size(); ++j) {
                if (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }
};

2. Optimized

class Solution {
public:
    int longestPalindromeSubseq(string &s) {
        const int n = s.size() + 1;
        int dp[n][n];
        memset(dp, 0, n * n * sizeof(int));
        for (int i = 1; i <= n - 1; ++i) {
            for (int j = 1; j <= n - 1; ++j) {
                if (s[i - 1] == s[n - j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n - 1][n - 1];
    }
};

• #dp

• #lcs