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.

1. class Solution:
   
2.     def longestPalindromeSubseq(self, s: str) -> int:
   
3.         if s == None or len(s) == 0:
   
4.             return 0
   
5.         res = 0
   
6.         N = len(s)
   
7.         dp = [[0 for _ in range(N)] for _ in range(N)]
   
8.         
   
9.         for i in range(N):
   
10.             dp[i][i] = 1
    
11.             res = max(res, dp[i][i])
    
12.         
    
13.         
    
14.         for length in range(1, N):
    
15.             for i in range(N - length):
    
16.                 j = i + length
    
17.                 if s[i] == s[j]:
    
18.                     dp[i][j] = dp[i + 1][j - 1] + 2
    
19.                 else:
    
20.                     dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
    
21.                
    
22.                 res = max(res, dp[i][j])
    
23.         # print(dp)
    
24.         return res

复制代码