LeetCode 5. 最长回文子串

Skyme2026/9/17大约 5 分钟

LeetCode 5. 最长回文子串

题目核心

给你一个字符串 s，找到 s 中最长的回文子串并返回它。

输入：s = "babad"
输出："bab"（"aba" 同样有效）

输入：s = "cbbd"
输出："bb"

输入：s = "a"
输出："a"

回文子串是连续的，这一点和子序列题不同。

解题思考过程

第一步：暴力枚举

枚举所有子串 s[i..j] 再判断回文：

时间复杂度：O(n³)
空间复杂度：O(1)

n 到 1000 时太慢。

第二步：区间 DP

令 dp[i][j] 表示 s[i..j] 是否回文：

dp[i][j] = (s[i] === s[j]) && dp[i+1][j-1]

边界：长度 1 必回文；长度 2 时只看两个字符是否相等。

时间复杂度：O(n²)
空间复杂度：O(n²)

能过，但空间还能再省。

第三步：中心扩展

回文串天然关于中心对称。不枚举子串的起止，反过来枚举回文中心，再向左右两边扩展：

奇数长度（"aba"）：中心是一个字符，从 (i, i) 起扩。
偶数长度（"abba"）：中心在两个字符之间，从 (i, i+1) 起扩。

总共 2n - 1 个中心，每个中心用双指针一路扩到"越界或两端不相等"为止。

时间复杂度：O(n²)
空间复杂度：O(1)

每次扩展结束后，用本次找到的回文和全局最长的比较、更新。

与 647 题的关系

647 - 回文子串用同一套奇偶中心扩展，只是那题统计回文子串的个数，本题记录其中最长的那一个。核心技巧完全互通，可以对照复习。

当前解法：中心扩展

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  let maxWindow = '';

  function expand(left, right) {
    // 没越界且两端相等，继续向两边扩
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }

    // 退出循环时已多走一步，真实回文区间是 [left+1, right-1]
    if (right - 1 - (left + 1) + 1 > maxWindow.length) {
      maxWindow = s.slice(left + 1, right);
    }
  }

  for (let i = 0; i < s.length; i++) {
    expand(i, i);       // 奇数长度，例如 "aba"
    expand(i, i + 1);   // 偶数长度，例如 "abba"
  }

  return maxWindow;
};

代码逐行解释

全局答案

let maxWindow = '';

记录目前找到的最长回文子串。题目保证 s 非空，但即使第一个字符进入比较，长度 1 也大于 0，能正常更新。

扩展函数

function expand(left, right) {
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    left--;
    right++;
  }
  ...
}

三个循环条件的顺序有讲究：先判越界，再访问字符。如果把 s[left] === s[right] 放前面，指针越界时读到 undefined，比较虽然通常也返回 false 并退出，但语义不干净。

退出循环后：回文区间在哪里？

退出 while 有两种原因：越界，或两端不相等。无论哪种，最后一次成功扩展对应的区间是 [left+1, right-1]。

长度 = (right - 1) - (left + 1) + 1 = right - left - 1

更新最长回文

if (right - 1 - (left + 1) + 1 > maxWindow.length) {
  maxWindow = s.slice(left + 1, right);
}

长度比较等价于 right - left - 1 > maxWindow.length。

s.slice(left + 1, right) 的结束位置是开区间，正好截到 right - 1，与真实回文区间一致。

枚举所有中心

for (let i = 0; i < s.length; i++) {
  expand(i, i);       // 奇中心
  expand(i, i + 1);   // 偶中心
}

最后一个位置的偶中心 expand(n-1, n) 会因为右指针越界立刻退出，不会出错。

执行过程示例

以 s = "cbbd" 为例：

i=0:
  expand(0,0): "c" 回文 → 扩到 (-1,1) 退出；maxWindow="c"
  expand(0,1): s[0]="c" ≠ s[1]="b"，立刻退出（回文是 [1,0]？——
                一次都没进循环，真实区间 [left+1,right-1]=[1,0] 为空，
                长度 right-left-1 = 0，不更新）
i=1:
  expand(1,1): "b" → 扩到 (0,2)，s[0]="c"≠s[2]="b" 退出；
                真实回文 [1,1] 长度 1，不替换 "c"（等长）
  expand(1,2): "bb" 回文 → 扩到 (0,3) 右越界退出；
                真实回文 [1,2] 长度 2 > 1；maxWindow = slice(1,3) = "bb"
i=2:
  expand(2,2): "b" → 长度 1，不更新
  expand(2,3): 右越界，长度 0，不更新
i=3:
  expand(3,3): "d" → 长度 1，不更新
  expand(3,4): 越界

返回 "bb"

复杂度分析

时间复杂度：O(n²) — 2n-1 个中心，每个最多扩 O(n)
空间复杂度：O(1)

替代写法：动态规划

var longestPalindrome = function (s) {
  const n = s.length;
  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 <= n; i++) {
      const j = i + len - 1;

      if (len === 1) {
        dp[i][j] = true;
      } else if (len === 2) {
        dp[i][j] = s[i] === s[j];
      } else {
        dp[i][j] = s[i] === s[j] && dp[i + 1][j - 1];
      }

      if (dp[i][j] && len > maxLen) {
        maxLen = len;
        start = i;
      }
    }
  }

  return s.slice(start, start + maxLen);
};

必须保证 dp[i+1][j-1] 先算好，所以外层按长度枚举（不能简单按行号）。

进阶了解：Manacher 算法

通过插入统一分隔符把奇偶情况归一化，再利用已求得的回文半径做对称复用，可以做到：

时间复杂度：O(n)
空间复杂度：O(n)

面试中写出中心扩展通常已经足够，Manacher 属于知道思想即可的加分项。

易错点

漏掉偶数中心：只写 expand(i, i) 会让 "bb"、"abba" 这类答案全部找不到。
退出循环后区间错位：真实回文是 [left+1, right-1]，切片要用 slice(left+1, right)；直接 slice(left, right) 会把不相等的两端切进去。
长度公式记错：right - left - 1，不是 right - left + 1。
一次都没进 while 时长度为 0：中心两端不相等（如 expand(0,1) 且字符不同），不应更新答案，长度比较天然拦住，别额外写入空串。
DP 枚举顺序：依赖更短的子串结果，外层必须是子串长度；写反会读到尚未计算的状态。