跳到主要内容

最长回文子串

问题​

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

示例：

输入：s = "babad"
输出："bab" 或 "aba"

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

来源：LeetCode 5. 最长回文子串

回文串

正读和反读都一样的字符串，如 "aba"、"abba"、"a"。

答案​

方法一：中心扩展（推荐）​

核心思路：以每个字符（和每两个相邻字符之间的空隙）作为中心，向两边扩展，找最长回文。

longestPalindrome.ts
function longestPalindrome(s: string): string {
  let start = 0;
  let maxLen = 1;

  function expandAroundCenter(left: number, right: number): void {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      const len = right - left + 1;
      if (len > maxLen) {
        start = left;
        maxLen = len;
      }
      left--;
      right++;
    }
  }

  for (let i = 0; i < s.length; i++) {
    // 奇数长度回文：以 i 为中心
    expandAroundCenter(i, i);
    // 偶数长度回文：以 i 和 i+1 之间为中心
    expandAroundCenter(i, i + 1);
  }

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

图解：

s = "babad"

i=0 'b': 扩展(0,0) → "b"(len=1)
         扩展(0,1) → s[0]='b' ≠ s[1]='a' → 不扩展

i=1 'a': 扩展(1,1) → "a" → 扩展 s[0]='b' ≠ s[2]='b'? 不对
         等等...实际 s[0]='b'=s[2]='b'? 不，s="babad"
         扩展(1,1): s[0]='b' vs s[2]='b' → 相等! → "bab"(len=3) ✓
         继续: s[-1] 越界 → 停止
         扩展(1,2): s[1]='a' ≠ s[2]='b' → 不扩展

i=2 'b': 扩展(2,2): s[1]='a' vs s[3]='a' → 相等! → "aba"(len=3)
         继续: s[0]='b' vs s[4]='d' → 不等 → 停止

最终：maxLen=3，start=0，返回 "bab"
复杂度分析
  • 时间复杂度：O(n2)O(n^2) — n 个中心，每个最多扩展 O(n)O(n)
  • 空间复杂度：O(1)O(1) — 只用几个变量

方法二：动态规划​

状态定义：dp[i][j] 表示 s[i..j] 是否是回文串。

转移方程：

dp[i][j]=(s[i]===s[j])∧dp[i+1][j−1]dp[i][j] = (s[i] === s[j]) \wedge dp[i+1][j-1]
longestPalindromeDP.ts
function longestPalindrome(s: string): string {
  const n = s.length;
  // 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 i = 0; i < n; i++) dp[i][i] = true;

  // 从长度 2 开始填表
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;

      if (s[i] === s[j]) {
        if (len === 2 || dp[i + 1][j - 1]) {
          dp[i][j] = true;
          if (len > maxLen) {
            start = i;
            maxLen = len;
          }
        }
      }
    }
  }

  return s.substring(start, start + maxLen);
}
复杂度
  • 时间复杂度：O(n2)O(n^2)
  • 空间复杂度：O(n2)O(n^2) — dp 表

空间不如中心扩展法，但 DP 更容易扩展到其他变体。

方法三：Manacher 算法（O(n)O(n)，了解即可）​

Manacher 算法是求最长回文子串的最优算法，时间复杂度 O(n)O(n)：

longestPalindromeManacher.ts
function longestPalindrome(s: string): string {
  // 预处理：在每个字符间插入 '#'，统一奇偶
  // "babad" → "#b#a#b#a#d#"
  const t = '#' + s.split('').join('#') + '#';
  const n = t.length;
  const p = new Array(n).fill(0); // p[i] = 以 i 为中心的最长回文半径

  let center = 0; // 当前最右回文的中心
  let right = 0;  // 当前最右回文的右边界

  for (let i = 0; i < n; i++) {
    // 利用对称性初始化
    if (i < right) {
      const mirror = 2 * center - i;
      p[i] = Math.min(right - i, p[mirror]);
    }

    // 尝试扩展
    while (
      i + p[i] + 1 < n &&
      i - p[i] - 1 >= 0 &&
      t[i + p[i] + 1] === t[i - p[i] - 1]
    ) {
      p[i]++;
    }

    // 更新最右边界
    if (i + p[i] > right) {
      center = i;
      right = i + p[i];
    }
  }

  // 找最大的 p[i]
  let maxLen = 0;
  let maxCenter = 0;
  for (let i = 0; i < n; i++) {
    if (p[i] > maxLen) {
      maxLen = p[i];
      maxCenter = i;
    }
  }

  // 转换回原字符串的索引
  const start = (maxCenter - maxLen) / 2;
  return s.substring(start, start + maxLen);
}
Manacher 算法
  • 时间复杂度：O(n)O(n) — 每个位置最多被扩展一次
  • 空间复杂度：O(n)O(n)
  • 面试中一般不要求写出来，但知道有 O(n)O(n) 解法是加分项

常见面试追问​

Q1: 如何判断一个字符串是否是回文？​

答案：双指针从两端向中间比较：

function isPalindrome(s: string): boolean {
  let left = 0;
  let right = s.length - 1;
  while (left < right) {
    if (s[left] !== s[right]) return false;
    left++;
    right--;
  }
  return true;
}

Q2: 最长回文子序列？(LeetCode 516)​

答案：注意是子序列（可不连续），经典 DP：

function longestPalindromeSubseq(s: string): number {
  const n = s.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(0));

  for (let i = n - 1; i >= 0; i--) {
    dp[i][i] = 1;
    for (let j = i + 1; j < n; j++) {
      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][n - 1];
}

Q3: 回文子串的数量？(LeetCode 647)​

答案：中心扩展法，每次扩展成功就计数 +1：

function countSubstrings(s: string): number {
  let count = 0;

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

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

  return count;
}

相关链接​