516.最长回文子序列.md

516.最长回文子序列

/*
 * @lc app=leetcode.cn id=516 lang=typescript
 *
 * [516] 最长回文子序列
 */

// @lc code=start
function longestPalindromeSubseq(s: string): number {}
// @lc code=end

解法 1: 动态规划

• 通过反转字符串得到 s1,找到 s 和 s1 两个字符串中相等的最长子序列,既为题目的答案
• dp[i][j] 表示 s[0..i] 和反转后 s1[0..j] 相等的子序列长度

  s[i] === s1[j] ? (dp[i][j] = dp[i - 1][j - 1] + 1) : (dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]))

function longestPalindromeSubseq(s: string): number {
  const n = s.length
  const dp: number[][] = new Array(n).fill(0).map(() => [])
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (s[i] === s[n - j - 1]) {
        dp[i][j] = (dp[i - 1]?.[j - 1] ?? 0) + 1
      } else {
        dp[i][j] = Math.max(dp[i - 1]?.[j] ?? 0, dp[i][j - 1] ?? 0)
      }
    }
  }

  return dp[n - 1][n - 1]
}

优化空间

function longestPalindromeSubseq(s: string): number {
  const n = s.length
  const dp: number[] = new Array(n).fill(0)

  for (let i = 0; i < n; i++) {
    let pre = 0
    for (let j = 0; j < n; j++) {
      if (s[i] === s[n - j - 1]) [dp[j], pre] = [pre + 1, dp[j]]
      else [dp[j], pre] = [Math.max(dp[j], dp[j - 1] ?? 0), dp[j]]
    }
  }

  return dp[n - 1]
}

Case

test.each([
  { input: { s: 'bbbab' }, output: 4 },
  { input: { s: 'cbbd' }, output: 2 },
])('input: s = $input.s', ({ input: { s }, output }) => {
  expect(longestPalindromeSubseq(s)).toEqual(output)
})