LeetCode 647. 回文子串

约 5 分钟
文章信息 16 个分类 3 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 20-50 腾讯 字节 华为 亚马逊 美团 京东 百度 快手 虾皮 猿辅导
标签
字符串 动态规划 双指针

题目描述

✅ 647. 回文子串

image-20260928200317056

题意分析

统计字符串中有多少个连续区间正着读、反着读都相同，即回文子串的数量。每个非空区间按起止下标区分，即使内容相同，只要位置不同也分别计数。

单个字符也是回文，奇数长度和偶数长度都要统计。只返回数量，不需要列出字符串，也不能按内容用集合去重；子串必须连续，不能跳过中间字符。

解法：中心扩展

核心思路

[!blue]

回文的两侧关于中心对称。若一个内部区间已经是回文，只要它外侧新增的两个字符相等，更大的区间仍是回文，因此可以从中心开始逐层验证，而不必为每个区间重新检查所有字符。

奇数长度的中心是某个字符，从 (i, i) 开始；偶数长度的中心在相邻字符之间，从 (i, i + 1) 开始。对每个下标分别启动这两种扩展，就覆盖了全部可能的中心。

扩展过程中，只要左右下标有效且字符相等，当前区间就是一个回文，计数加一，再同时向外移动。第一次比较时，奇数中心内部只有一个字符，偶数中心内部为空，二者都满足回文基础条件。

若一对字符不相等，同中心的所有更大区间都会包含这对不匹配字符，所以可以立即停止。计数应在每次扩展成功时增加，同一中心可以对应多个不同长度的回文，而不是只记录最长的一个。

任意回文区间都有唯一的中心与长度，必然在对应中心的某一轮扩展中被计算，其他中心不会生成同一个区间，因此不重不漏。末尾的偶数中心右侧越界，直接贡献零，不影响结果。

解题步骤

  1. 遍历每个下标 i，分别调用扩展函数处理 (i, i) 和 (i, i + 1)。
  2. 扩展函数先检查两端下标，再比较字符；有效且相等时计数加一。
  3. 执行 left--、right++，继续检查更大区间，直到越界或失配。
  4. 累加每个中心的扩展次数，返回全部回文区间的数量。

代码实现

class Solution {
    public int countSubstrings(String s) {
        int ans = 0;

        for (int center = 0; center < s.length(); center++) {
            ans += expand(s, center, center);
            // 字符之间作为偶数回文中心，和单字符中心互补且不会重复。
            ans += expand(s, center, center + 1);
        }

        return ans;
    }

    private int expand(String s, int left, int right) {
        int count = 0;

        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            // 每成功扩展一层，恰好多出一个以当前中心确定的回文子串。
            count++;
            left--;
            right++;
        }

        return count;
    }
}

func countSubstrings(s string) int {
    ans := 0
    for center := 0; center < len(s); center++ {
        ans += expandPalindrome(s, center, center)
        // 字符之间作为偶数回文中心，和单字符中心互补且不会重复。
        ans += expandPalindrome(s, center, center+1)
    }
    return ans
}

func expandPalindrome(s string, left int, right int) int {
    count := 0
    for left >= 0 && right < len(s) && s[left] == s[right] {
        // 每成功扩展一层，恰好多出一个以当前中心确定的回文子串。
        count++
        left--
        right++
    }
    return count
}

复杂度分析

  • 时间复杂度：$O(n^2)$。共有 $2n-1$ 个中心，每个中心最坏向外扩展 $O(n)$ 层；全相同字符串会达到该上界。
  • 空间复杂度：$O(1)$，只使用计数器和左右指针。

关键点总结

[!green]

  • 回文既可能以字符为中心，也可能以两个字符之间的空隙为中心。
  • “中心 + 扩展半径”唯一确定一个回文子串，这是不重不漏的依据。
  • 本题按下标区间计数，不按字符串内容去重。
  • 与“最长回文子串”共用同一扩展模板：本题每次成功就计数，后者更新最长区间。

易错点总结

[!yellow]

  • 只枚举字符中心会漏掉偶数长度回文，必须同时处理字符之间的中心。
  • 按内容去重会合并不同位置的区间，与题目按出现位置计数的要求不符。
  • 内层已经失配时不能继续外扩，外层相等无法修复内部的不对称。
  • 必须先判断边界再访问字符，扩展后的下标可能为负或达到字符串长度。
  • 每次成功扩展都形成一个新区间，不能每个中心只计一次，也不能只计最长回文。

相似题目

题目 难度 关联与区别
5. 最长回文子串 中等 同样可中心扩展，原题保留最长区间，本题把每次成功扩展计为一个回文子串。
516. 最长回文子序列 中等 原题是可跳过字符的子序列，本题要求连续区间，状态与扩展方式不同。
131. 分割回文串 中等 用区间或中心扩展刻画回文结构；本题累计所有回文子串数量，该题预处理回文后枚举切分方案。
132. 分割回文串 II 困难 用区间或中心扩展刻画回文结构；本题累计所有回文子串数量，该题在回文区间上递推最少切割次数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/56601069
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！