Given a string s
, find the longest palindromic subsequence's length in s
.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: s = "bbbab" Output: 4 Explanation: One possible longest palindromic subsequence is "bbbb".
Example 2:
Input: s = "cbbd" Output: 2 Explanation: One possible longest palindromic subsequence is "bb".
Constraints:
1 <= s.length <= 1000
s
consists only of lowercase English letters.dp(l, r)
denote the length of the longest palindromic subsequence of s[l..r]
.s[l] == s[r]
then dp[l][r] = dp[l+1][r-1] + 2
s[l] != s[r]
then dp[l][r] = max(dp[l+1][r], dp[l][r-1])
.dp(0, n-1)
is our result.def longestPalindromeSubseq(s: str) -> int: r = len(s) - 1 cache = {} # (l, r) longest string = r -l def dp(l, r): if l > r: return 0 if l == r: return 1 if (l, r) in cache: return cache[(l, r)] if s[l] == s[r]: cache[(l, r)] = 2 + dp(l + 1, r - 1) else: cache[(l, r)] = max(dp(l, r - 1), dp(l + 1, r)) return cache[(l, r)] return dp(0, r)
If you like dEexams.com and would like to contribute, you can write your article here or mail your article to admin@deexams.com . See your article appearing on the dEexams.com main page and help others to learn.