Skip to main content

516. Longest Palindromic Subsequence

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

Python​

Top Down DP​

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        dp = [
            [0 for _ in range(len(s))]
            for _ in range(len(s))
        ]

        for k in range(1, len(s) + 1):
            for i in range(len(s) - k + 1):
                j = k + i - 1
                if i == j:
                    dp[i][j] = 1
                elif i + 1 == j and s[i] == s[j]:
                    dp[i][j] = 2
                elif 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][-1]

Javascript​

var longestPalindromeSubseq = function(s) {
    const memo = {};
    const dp = (i, j) => {
        if (!memo[i]) memo[i] = {};
        if (i > j) return 0;
        if (i === j) return 1
        if (memo[i][j]) return memo[i][j];

        if (s[i] === s[j]) {
            memo[i][j] = dp(i + 1, j - 1) + 2;
        } else {
            memo[i][j] = Math.max(dp(i + 1, j), dp(i, j - 1));
        }

        return memo[i][j];
    }
    return dp(0, s.length - 1)
}