5.最长回文子串

LeetCode 原题链接 题目

1. dp 数组含义

定义二维数组 dp：

dp[i][j] 表示字符串 s 从下标 i 到下标 j 的子串 s[i...j] 是否是回文子串。

如果 dp[i][j] === true，说明：

s[i...j] 是回文子串。

如果 dp[i][j] === false，说明：

s[i...j] 不是回文子串。

题目要求返回最长回文子串本身，所以在计算 dp 的过程中，还需要记录：

  • start：当前最长回文子串的起始下标。
  • maxLen：当前最长回文子串的长度。

最后返回：

s.slice(start, start + maxLen)

2. 确定状态转移方程

判断 s[i...j] 是否是回文子串，关键看两端字符：

s[i]
s[j]

两端字符不同

如果：

s[i] !== s[j]

那么 s[i...j] 一定不是回文子串：

dp[i][j] = false;

两端字符相同

如果：

s[i] === s[j]

还需要分两种情况。

第一种，子串长度小于等于 3：

j - i + 1 <= 3

只要两端字符相同，它一定是回文子串。

例如：

"a"
"aa"
"aba"

所以：

dp[i][j] = true;

第二种，子串长度大于 3。

此时只看两端字符还不够，还要看去掉两端后的内部子串 s[i + 1...j - 1] 是否是回文子串：

dp[i][j] = dp[i + 1][j - 1];

完整转移方程：

if (s[i] !== s[j]) {
  dp[i][j] = false;
} else if (j - i + 1 <= 3) {
  dp[i][j] = true;
} else {
  dp[i][j] = dp[i + 1][j - 1];
}

一句话总结：一个子串是否是回文，取决于两端字符是否相同，以及去掉两端后的内部子串是否是回文。

3. dp 数组如何初始化

dp[i][j] 表示某个子串是否是回文子串，一开始还没有判断任何子串，所以可以全部初始化为 false：

const dp = Array.from({ length: n }, () => new Array(n).fill(false));

根据状态定义，单个字符一定是回文子串：

dp[i][i] = true

不过在本题代码中，不需要提前单独初始化对角线。

因为遍历子串长度 len = 1 时，s[i] === s[j] 且 len <= 3，会自然把 dp[i][i] 更新为 true。

边界情况：

  • 如果 s.length < 2，字符串本身就是最长回文子串，直接返回 s。
  • 初始设置 start = 0、maxLen = 1，表示至少可以把第一个字符作为当前最长回文子串。

4. 确定遍历顺序

状态转移中：

dp[i][j] 依赖 dp[i + 1][j - 1]

也就是当前子串依赖它内部更短的子串。

所以必须先计算短子串，再计算长子串。

可以按子串长度从小到大遍历：

for (let len = 1; len <= n; len++) {
  for (let i = 0; i + len - 1 < n; i++) {
    const j = i + len - 1;
    // 计算 dp[i][j]
  }
}

这样在计算长度为 len 的子串时，内部子串 s[i + 1...j - 1] 的长度是 len - 2，一定已经在前面计算完成。

5. 举例打印 dp 数组

以：

s = "babad"

为例。

下标和字符对应关系：

下标： 0  1  2  3  4
字符： b  a  b  a  d

初始化时，dp 全部为 false：

i \ j01234
0falsefalsefalsefalsefalse
1falsefalsefalsefalsefalse
2falsefalsefalsefalsefalse
3falsefalsefalsefalsefalse
4falsefalsefalsefalsefalse

长度为 1

每个单字符都是回文子串：

i \ j01234
0truefalsefalsefalsefalse
1falsetruefalsefalsefalse
2falsefalsetruefalsefalse
3falsefalsefalsetruefalse
4falsefalsefalsefalsetrue

此时最长回文子串长度是 1。

长度为 2

检查 "ba"、"ab"、"ba"、"ad"，两端字符都不同，所以没有新的回文子串。

长度为 3

检查 "bab"：

s[0] === s[2]

并且长度为 3，所以：

dp[0][2] = true;

当前最长回文子串更新为 "bab"。

继续检查 "aba"：

s[1] === s[3]

并且长度为 3，所以：

dp[1][3] = true;

"aba" 也是长度为 3 的回文子串。

最终 dp 数组为：

i \ j01234
0truefalsetruefalsefalse
1falsetruefalsetruefalse
2falsefalsetruefalsefalse
3falsefalsefalsetruefalse
4falsefalsefalsefalsetrue

最长回文子串长度是 3，返回 "bab" 或 "aba" 都可以。

由于下面的代码只在发现更长回文子串时更新答案，所以先找到 "bab" 后，不会被同长度的 "aba" 覆盖，最终返回 "bab"。

6. 代码实现

var longestPalindrome = function (s) {
  const n = s.length;

  // 长度为 0 或 1 时，字符串本身就是最长回文子串
  if (n < 2) return s;

  // dp[i][j] 表示 s[i...j] 是否是回文子串
  const dp = Array.from({ length: n }, () => new Array(n).fill(false));

  // 记录当前最长回文子串的起始位置和长度
  let start = 0;
  let maxLen = 1;

  // 先枚举子串长度，保证内部更短的子串已经计算过
  for (let len = 1; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;

      if (s[i] !== s[j]) {
        // 两端字符不同，一定不是回文子串
        dp[i][j] = false;
      } else if (len <= 3) {
        // 长度为 1、2、3 时，两端相同即可确定是回文
        dp[i][j] = true;
      } else {
        // 长度大于 3 时，取决于内部子串是否是回文
        dp[i][j] = dp[i + 1][j - 1];
      }

      if (dp[i][j] && len > maxLen) {
        // 找到更长的回文子串，更新答案位置
        start = i;
        maxLen = len;
      }
    }
  }

  // 根据起始位置和长度截取最长回文子串
  return s.slice(start, start + maxLen);
};

复杂度分析

  • 时间复杂度：O(n^2)，需要枚举所有子串。
  • 空间复杂度：O(n^2)，需要二维 dp 数组保存状态。