Longest Palindromic Subsequence
Description
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:
4One possible longest palindromic subsequence is "bbbb".
Example 2:
Input:
"cbbd"Output:
2One possible longest palindromic subsequence is "bb".
Constraints:
1 <= s.length <= 1000
s
consists only of lowercase English letters.
Solution(javascript)
// const longestPalindromeSubseq = (s = '') => {
// const { length } = s
// const dp = new Array(length).fill(0).map(() => new Array(length).fill(0))
// for (let right = 0; right < length; right++) {
// dp[right][right] = 1
// // 这里这里的依赖顺序
// for (let left = right - 1; left >= 0; left--) {
// if (s[left] === s[right]) {
// dp[left][right] = dp[left + 1][right - 1] + 2
// } else {
// dp[left][right] = Math.max(dp[left + 1][right], dp[left][right - 1])
// }
// }
// }
// return dp[0][length - 1]
// }
// recursive with memo
const longestPalindromeSubseq = (s = '') => {
const memo = new Array(s.length).fill(0).map(() => new Array(s.length).fill(undefined))
const aux = (left, right) => {
if (memo[left][right] !== undefined) {
return memo[left][right]
}
if (left === right) {
return 1
}
if (left > right) {
return 0
}
if (s[left] === s[right]) {
memo[left][right] = 2 + aux(left + 1, right - 1)
return memo[left][right]
}
memo[left][right] = Math.max(aux(left + 1, right), aux(left, right - 1))
return memo[left][right]
}
return aux(0, s.length - 1)
}