算法 - 最长回文子串（中心扩散法）

Posted on

1. 题目

给你一个字符串 s，找到其中最长的回文子串。回文指正读反读都一样。

示例:

1
2
3
4
5
输入: s = "babad"
输出: "bab"（"aba" 同样是合法答案）

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

2. 解题思路

2.1 中心扩散（推荐，直观且高效）

回文串一定围绕某个「中心」对称展开。长度为 n 的字符串共有 2n - 1 个中心：

  • n 个单字符中心（产生奇数长度回文，如 “aba”）。
  • n - 1 个双字符间隙中心（产生偶数长度回文，如 “abba”）。

枚举每个中心，向两边同时扩展直到不再相等，记录最长的一段。每个中心调用一次扩散函数，分别以 i（奇）和 i, i+1（偶）为初始左右指针。

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

2.2 动态规划 O(n²) 空间

dp[i][j] 表示 s[i..j] 是否回文：dp[i][j] = (s[i]===s[j]) && dp[i+1][j-1]。按长度从小到大填表。空间更大，思路清晰可作为对照。

存在 O(n) 的 Manacher 算法，面试一般不要求手写，能提名字并说明它是「利用已知回文的对称性避免重复扩展」即为加分。

3. TypeScript 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function longestPalindrome(s: string): string {
    if (s.length < 2) return s;

    let start = 0;
    let maxLen = 1;

    // 从 (left, right) 向两边扩散，返回回文长度
    function expand(left: number, right: number): number {
        while (left >= 0 && right < s.length && s[left] === s[right]) {
            left--;
            right++;
        }
        return right - left - 1; // 注意循环退出时各多走了一步
    }

    for (let i = 0; i < s.length; i++) {
        const oddLen = expand(i, i);     // 奇数中心
        const evenLen = expand(i, i + 1); // 偶数中心
        const len = Math.max(oddLen, evenLen);

        if (len > maxLen) {
            maxLen = len;
            // 由中心反推起点：奇偶统一用这个式子
            start = i - Math.floor((len - 1) / 2);
        }
    }

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

console.log(longestPalindrome("babad")); // "bab" 或 "aba"
console.log(longestPalindrome("cbbd"));  // "bb"
console.log(longestPalindrome("a"));     // "a"

4. 面试延伸

  • 起点公式 i - (len-1)/2 是易错点：奇偶都适用，因为 (len-1)/2 向下取整正好覆盖两种中心的偏移差异。
  • 最长回文子序列（516）：子序列可不连续，转成「s 与 reverse(s) 的 LCS」或区间 DP dp[i][j]，别和本题混淆。
  • Manacher：把 O(n²) 优化到 O(n)，核心是维护「右边界最大的回文」及其对称中心，复用已知信息。
  • 字符串匹配类（回文、子串、子序列）先问自己：中心？双指针？区间 DP？——建立这三选一的直觉。

难度：中等 | LeetCode 5 题 | 中心扩散模板