Longest Palindromic Subsequence

• Lintcode : 667 / Leetcode : 516
• Level : Medium

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
Example1

Input: "bbbab"
Output: 4
Explanation:
One possible longest palindromic subsequence is "bbbb".
Example2

Input: "bbbbb"
Output: 5

Concept & Algorithm

筆記

Time Complexity & Space Complexity

time : O(n ^ 2)
space: O(n ^ 2)

Answer

class Solution {
public:
    int longestPalindromeSubseq(string &s) {
        int len = s.size();
        if (len == 0) return 0;
        vector<vector<int>> dp(len, vector<int>(len, 0));
        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;
            for (int j = i - 1; j >= 0; j--) {
                if (s[i] == s[j]) {
                    dp[j][i] = dp[j + 1][i - 1] + 2;
                }else {
                    dp[j][i] = max(dp[j + 1][i], dp[j][ i - 1]);
                }
            }
        }
        return dp[0][len - 1];
    }
};

tags: DP

​