LeetCode 647. 回文子串

题目核心

给你一个字符串 s，请你统计并返回这个字符串中回文子串的数目。

• 具有不同开始位置或结束位置的子串，即使由相同字符组成，也会被视作不同的子串。
• 单个字符本身也算回文子串。

例如：

s = "abc"
答案：3（"a"、"b"、"c"）

s = "aaa"
答案：6（"a"×3、"aa"×2、"aaa"×1）

解题思考过程

第一步：理解问题

回文子串是正着读反着读一样的子串。题目要统计所有回文子串的个数，而不只是找最长的那一个。

注意：单个字符也是回文，所以答案至少是字符串的长度（每个字符算一个）。

第二步：暴力解法（枚举所有子串）

最直接的思路：枚举所有可能的子串，逐个判断是否回文。

枚举起点 i，枚举终点 j（0 ≤ i ≤ j < n），判断 s[i...j] 是否回文。

时间复杂度：O(n³) - 枚举 O(n²) 个子串，每个判断回文 O(n)
空间复杂度：O(1)

时间太慢，n 稍大就会超时。

第三步：想到动态规划

令 dp[i][j] 表示 s[i...j] 是否回文。递推关系：

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

两端字符相同，且去掉两端后的子串回文，那么整段就是回文。

时间复杂度：O(n²)
空间复杂度：O(n²) - 二维 dp 数组

时间 OK，但 O(n²) 空间能不能再降？

第四步：想到中心扩展

回文串有一个天然性质——对称。如果反过来想：不枚举子串的起止，而是枚举回文的中心，然后向两边扩散，看看能扩出多少回文。

回文中心有两种情况：

• 奇数长度回文：中心是某个字符（如 aba，中心是 b）。
• 偶数长度回文：中心在两个字符之间（如 abba，中心在两个 b 之间）。

所以对每个位置 i，要枚举两种中心：

• 中心为 i（奇数长度）：dfs(i, i)
• 中心为 i 和 i+1 之间（偶数长度）：dfs(i, i+1)

每次扩散成功（左右字符相同），就说明找到一个新的回文子串，计数 +1。

第五步：验证中心扩展

以 s = "aaa" 为例：

奇数中心 dfs(i, i)：
  dfs(0,0): "a" ✓ → 扩 dfs(-1,1) 越界，共 1 个
  dfs(1,1): "a" ✓ → 扩 dfs(0,2) "aaa" ✓ → 扩 dfs(-1,3) 越界，共 2 个
  dfs(2,2): "a" ✓ → 扩 dfs(1,3) 越界，共 1 个
  合计 4 个

偶数中心 dfs(i, i+1)：
  dfs(0,1): "aa" ✓ → 扩 dfs(-1,2) 越界，共 1 个
  dfs(1,2): "aa" ✓ → 扩 dfs(0,3) 越界，共 1 个
  dfs(2,3): 越界，0 个
  合计 2 个

总数 4 + 2 = 6，正确！

第六步：复杂度

时间复杂度：O(n²) - 枚举 O(n) 个中心，每个中心最多向外扩 O(n) 次
空间复杂度：O(1)（迭代版）或 O(n)（DFS 版递归栈）

比 DP 更省空间。

当前解法：中心扩展 DFS

/**
 * @param {string} s
 * @return {number}
 */
var countSubstrings = function(s) {
  let count = 0;

  const dfs = (left, right) => {
    // 越界或者左右字符不同，结束
    if (
      left < 0 ||
      right >= s.length ||
      s[left] !== s[right]
    ) {
      return;
    }

    // 当前 s[left...right] 是回文串
    count++;

    // 继续向两边扩散
    dfs(left - 1, right + 1);
  };

  for (let i = 0; i < s.length; i++) {
    // 奇数长度回文
    dfs(i, i);

    // 偶数长度回文
    dfs(i, i + 1);
  }

  return count;
};

代码逐行解释

计数变量

let count = 0;

全局计数器，每找到一个回文子串就 count++。

中心扩展函数 dfs

const dfs = (left, right) => {

left 和 right 是当前考虑的子串两端的指针。它们一起组成了"回文中心"：

• 当 left == right 时，中心是一个字符（奇数长度）。
• 当 right == left + 1 时，中心在两个字符之间（偶数长度）。

递归终止条件

  if (
    left < 0 ||
    right >= s.length ||
    s[left] !== s[right]
  ) {
    return;
  }

三种情况结束扩展：

1. left < 0：左指针越出字符串开头。
2. right >= s.length：右指针越出字符串末尾。
3. s[left] !== s[right]：两端字符不同，不再是回文，没必要继续扩了。

找到回文，计数

  count++;

如果通过了上面的检查，说明 s[left...right] 是回文子串，计数 +1。

继续向两边扩散

  dfs(left - 1, right + 1);

回文成功后，尝试往左右各扩一位，看看更大的子串是不是回文：

• 左边减 1，右边加 1。
• 这就是 DFS 的思想：一路扩到扩不动为止，自然返回。

枚举所有中心

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

每个位置 i 都要枚举两种中心：

• dfs(i, i)：中心就是 s[i]，长度为奇数。
• dfs(i, i + 1)：中心在 s[i] 和 s[i+1] 之间，长度为偶数。如果 i+1 超出长度，dfs 会立刻返回，不会出问题。

返回总数

return count;

执行过程示例

以 s = "aaa" 为例，逐步展示：

初始 count = 0

i=0:
  dfs(0,0) 奇数中心：
    s[0]=s[0]，count=1。扩 dfs(-1,1)
    dfs(-1,1)：left<0，返回
  dfs(0,1) 偶数中心：
    s[0]=a, s[1]=a，count=2。扩 dfs(-1,2)
    dfs(-1,2)：left<0，返回

i=1:
  dfs(1,1) 奇数中心：
    s[1]=s[1]，count=3。扩 dfs(0,2)
      dfs(0,2)：s[0]=a, s[2]=a，count=4。扩 dfs(-1,3)
        dfs(-1,3)：越界，返回
  dfs(1,2) 偶数中心：
    s[1]=a, s[2]=a，count=5。扩 dfs(0,3)
      dfs(0,3)：right>=3，返回

i=2:
  dfs(2,2) 奇数中心：
    s[2]=s[2]，count=6。扩 dfs(1,3)
      dfs(1,3)：right>=3，返回
  dfs(2,3) 偶数中心：
    right>=3，直接返回

最终 count = 6

为什么这种方法不会漏、不会重

• 不会漏：每个回文子串有且只有一个中心（奇数中心是中间字符，偶数中心是中间间隙），我们枚举了所有可能的中心，所以不会漏。
• 不会重：每个回文子串只会在它"唯一的中心"处被计数一次，不会重复计数。

这就是中心扩展法的正确性——回文子串和它的中心一一对应。

复杂度分析

• 时间复杂度：O(n²)。共有 2n - 1 个中心（n 个奇数中心、n-1 个偶数中心），每个中心最多向外扩散 O(n) 次。
• 空间复杂度：O(n)。DFS 递归深度最大是回文中心扩展到边界，最多 O(n/2) 级递归栈。如果想降到 O(1)，可以把 DFS 改成 while 循环迭代版（见下）。

替代写法：迭代版中心扩展

把递归改成 while 循环，避免递归栈空间：

var countSubstrings = function(s) {
  let count = 0;

  const expand = (left, right) => {
    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;
};

• 时间复杂度：O(n²)
• 空间复杂度：O(1)——最优的空间复杂度

逻辑和 DFS 版完全一致，只是把递归换成了 while 循环。

替代解法一：动态规划

var countSubstrings = function(s) {
  const n = s.length;
  const dp = Array.from({ length: n }, () => new Array(n).fill(false));
  let count = 0;

  // 从短到长枚举子串长度
  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]) count++;
    }
  }

  return count;
};

• 时间复杂度：O(n²)
• 空间复杂度：O(n²) — 空间不如中心扩展优

三种解法对比

解法	时间复杂度	空间复杂度	特点
DFS 中心扩展（当前）	O(n²)	O(n) 递归栈	思路直观，代码简洁
迭代中心扩展	O(n²)	O(1)	最优，无额外空间
动态规划	O(n²)	O(n²)	适合理解区间 DP 思想

易错点

1. 别忘了偶数长度回文：很多人只写了 dfs(i, i) 漏掉了 dfs(i, i+1)，会导致"aa"、"abba"这类偶数长度回文全部少算。

2. 扩散条件的顺序：left < 0 和 right >= s.length 要写在 s[left] !== s[right] 前面，先越界检查再访问字符，否则会读到 undefined 导致判断不正确。

3. 计数时机：必须是进入递归、判断通过后立即 count++，而不是扩散成功才计数——否则最内层（单字符）的回文会漏掉。