回文子序列与子串

回文类问题的状态如何定义？

• 状态: dp[i][j] 描述区间 [i, j] 的回文性质;
• 两种口径:
  • 求长度: dp[i][j] 为区间内最长回文子序列长度;
  • 求判定: dp[i][j] 为区间本身是否回文;
• 共同依赖: 两端字符相等时看内部区间 [i+1, j-1], 不等时收缩一端;

最长回文子序列如何转移？

• 问题: 求最长回文子序列长度, 可不连续 (516);
• 两端相等:
  • i === j: dp[i][j] = 1;
  • 否则: dp[i][j] = dp[i+1][j-1] + 2;
• 两端不等: dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
• 初值: 全部为 0;
• 答案: dp[0][size-1];
• 复杂度: 时间 O(n^2), 空间 O(n^2);

const longestPalindromeSubseq = (s) => {
  const size = s.length;
  const dp = Array.from({ length: size }, () => new Array(size).fill(0));
  for (let i = size - 1; i >= 0; i--) {
    for (let j = i; j < size; j++) {
      if (i === j) dp[i][j] = 1;
      else if (s[i] === s[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
      else dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
    }
  }
  return dp[0][size - 1];
};

最长回文子串如何转移？

• 问题: 求最长的回文连续子串 (5);
• 状态: dp[i][j] 为 s[i..j] 是否回文;
• 判别:
  • s[i] !== s[j]: 直接为假;
  • j === i 或 j === i + 1: 长度 1 或 2, 两端相等即为真;
  • 否则: dp[i][j] = dp[i+1][j-1];
• 答案: 记录最长时的起点与长度, 返回 s.slice(start, start + len);
• 与子序列的区别: 子串必须连续, 因此 s[i] !== s[j] 时不能收缩继承;
• 复杂度: 时间 O(n^2), 空间 O(n^2);

const longestPalindrome = (s) => {
  const n = s.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(false));
  let start = 0;
  let len = 0;
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      if (s[i] !== s[j]) continue;
      if (j - i <= 1) dp[i][j] = true;
      else dp[i][j] = dp[i + 1][j - 1];
      if (dp[i][j] && j - i + 1 > len) {
        start = i;
        len = j - i + 1;
      }
    }
  }
  return s.slice(start, start + len);
};

如何统计回文子串的个数？

• 问题: 统计所有回文子串的数量 (647);
• 复用: 沿用最长回文子串的判定表;
• 改动: 每得到 dp[i][j] === true 就令计数加一;
• 答案: 累计值;
• 复杂度: 时间 O(n^2), 空间 O(n^2);