Leetcode 516. Longest Palindromic Subsequence

Seawolf

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.

class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        if s == None or len(s) == 0:
            return 0
        res = 0
        N = len(s)
        dp = [[0 for _ in range(N)] for _ in range(N)]
        
        for i in range(N):
            dp[i][i] = 1
            res = max(res, dp[i][i])
        
        
        for length in range(1, N):
            for i in range(N - length):
                j = i + length
                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])
                
                res = max(res, dp[i][j])
        # print(dp)
        return res