最长回文子串

更新: 7/3/2026 字数: 0 字 时长: 0 分钟

LeetCode 第 5 题 · 中等 · 双指针 / 中心扩展 / 动态规划经典题

题目描述

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

回文串是指正着读和倒着读都一样的字符串，例如 "aba"、"abba"。子串必须是连续的一段。

回文的两种"中心"

回文串按长度分两类，扩展时的中心不同：

• 奇数长度（如 "aba"）：中心是单个字符，两侧对称；
• 偶数长度（如 "abba"）：中心是两个字符之间的缝隙。

这正是"中心扩展法"要分别处理两种中心的原因。

示例：

输入	输出	说明
"babad"	"bab"	"aba" 也是正确答案
"cbbd"	"bb"	偶数长度回文
"a"	"a"	单字符本身是回文
"ac"	"a"	无长度 >1 的回文，任取其一

思路拆解：从暴力到最优

第一步：暴力枚举（先解出来）

最直接的想法——枚举所有子串，逐个判断是否为回文，记录最长的那个。

• 两层循环确定子串起点 i、终点 j，共 个子串；
• 每个子串用双指针判断回文，。

总时间复杂度 ，能得到正确答案但太慢。

点击展开暴力解法（仅供理解，不推荐）

function longestPalindrome_bruteForce(s) {
  const isPalindrome = (l, r) => {
    while (l < r) {
      if (s[l] !== s[r]) return false;
      l++; r--;
    }
    return true;
  };

  let best = '';
  for (let i = 0; i < s.length; i++) {
    for (let j = i; j < s.length; j++) {
      if (j - i + 1 > best.length && isPalindrome(i, j)) {
        best = s.slice(i, j + 1);
      }
    }
  }
  return best;
}

第二步：中心扩展（最优，最好理解）

暴力法的浪费在于：判断每个子串都要从头比较。换个角度——回文一定关于中心对称，那我们就从中心往两边扩展。

关键观察：对每个可能的中心，只要两侧字符相等就继续向外扩，一旦不等或越界就停止。这样每个中心的扩展是"增量式"的，不重复比较。

一个长度为 n 的字符串共有 2n - 1 个中心：n 个单字符中心（奇数回文）+ n-1 个字符缝隙中心（偶数回文）。

核心思路

遍历每个中心，调用 expand(left, right) 向两侧扩展：

• 奇数中心：expand(i, i)，从单字符出发；
• 偶数中心：expand(i, i+1)，从两字符缝隙出发。

只要 s[left] === s[right] 就 left--、right++ 继续扩，记录扩到的最长区间。每个中心扩展 ，共 个中心，总时间 ，且空间只需 。

补充：动态规划解法（O(n²) 时间 / O(n²) 空间）

定义 dp[i][j] 表示子串 s[i..j] 是否为回文。转移：s[i]===s[j] 且内部 dp[i+1][j-1] 也是回文（或长度 ≤ 2）时，dp[i][j] = true。需按子串长度从小到大填表。它时间与中心扩展相同，但多花 空间，一般不如中心扩展划算。

function longestPalindrome_dp(s) {
  const n = s.length;
  if (n < 2) return s;
  const dp = Array.from({ length: n }, () => new Array(n).fill(false));
  let start = 0, maxLen = 1;
  for (let i = 0; i < n; i++) dp[i][i] = true; // 单字符回文
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      if (s[i] !== s[j]) continue;
      dp[i][j] = (len === 2) || dp[i + 1][j - 1];
      if (dp[i][j] && len > maxLen) { start = i; maxLen = len; }
    }
  }
  return s.slice(start, start + maxLen);
}

交互式动画演示

下面用样例 "cbbd" 完整演示中心扩展过程（含奇/偶两种中心）。点击 下一步 / 自动播放，观察每个中心如何向两侧扩展、字符相等时（绿色）继续、不等或越界时（红色）停止，以及最长回文区间的刷新：

中心扩展 · 最长回文子串演示

样例输入："cbbd"

c0

b1

b2

d3

▲

扩展窗口—

当前最长回文"c"

长度1

思路：枚举每一个「中心」，向左右对称扩展。中心分两类——单字符（奇数长度）和两字符之间（偶数长度）。

步骤 0 / 13

观察重点

• 紫色 ▲ 标记当前中心，会区分"奇中心"（单字符）与"偶中心"（缝隙）；
• L、R 是对称扩展的两个指针；两端字符相等亮绿色、不等亮红色；
• 蓝色底纹是当前记录到的最长回文；样例最终答案是 "bb"（偶中心命中）。

完整代码（JavaScript）

/**
 * 最长回文子串 —— 中心扩展，时间 O(n²)，空间 O(1)
 * @param {string} s
 * @return {string}
 */
function longestPalindrome(s) {
  if (s.length < 2) return s;

  let start = 0, maxLen = 1; // 至少单字符是回文

  // 从中心 (l, r) 向两侧扩展，返回本次回文长度
  const expand = (l, r) => {
    while (l >= 0 && r < s.length && s[l] === s[r]) {
      l--; r++; // 两端相等，继续向外扩
    }
    // 跳出时 l、r 已越界一格，真实区间是 [l+1, r-1]
    const len = r - l - 1;
    if (len > maxLen) {
      maxLen = len;
      start = l + 1;
    }
  };

  for (let i = 0; i < s.length; i++) {
    expand(i, i);     // 奇数长度中心（单字符）
    expand(i, i + 1); // 偶数长度中心（两字符缝隙）
  }

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

// 测试
console.log(longestPalindrome('babad')); // "bab"（或 "aba"）
console.log(longestPalindrome('cbbd'));  // "bb"
console.log(longestPalindrome('a'));     // "a"
console.log(longestPalindrome('ac'));    // "a"

复杂度分析

解法	时间复杂度	空间复杂度	说明
暴力枚举			枚举 子串，每个校验
动态规划			填 dp[i][j] 表，需按长度递推
中心扩展（推荐）			个中心，空间最优
Manacher 算法			线性最优，实现较复杂

其中 为字符串长度。中心扩展在时间与动态规划持平、空间上更优：

若追求线性时间，可用 Manacher 算法 达到 ，但实现复杂度较高，面试中中心扩展通常已足够。

边界与易错点

易错点清单

1. 奇偶两种中心都要枚举：只写 expand(i, i) 会漏掉 "cbbd" 这类偶数长度回文。必须同时调用 expand(i, i+1)。
2. 扩展后区间的还原：while 跳出时 l、r 已经各自多走一格，真实回文区间是 [l+1, r-1]，长度为 r - l - 1。这一步下标最容易算错。
3. 空串 / 单字符：s.length < 2 直接返回 s；单字符本身就是长度 1 的回文，maxLen 初值设为 1。
4. 偶中心越界保护：expand(i, i+1) 中 i+1 可能等于 n，靠 r < s.length 的判断兜住，不必额外特判。
5. 返回的是子串不是长度：本题要求返回字符串，用 s.slice(start, start + maxLen)；slice 第二参数是结束下标（不含），别写成 start + maxLen - 1。
6. 区分子串与子序列：回文子串必须连续，中心扩展天然满足；若题目改成回文子序列，需改用区间 DP。

一句话记忆

"从中心往两边照镜子"——枚举 2n-1 个中心（含单字符和缝隙两种），两端相等就往外扩，扩不动就停，记录最长的那段。