LeetCode 647. 回文子串
目录
题目描述
题意分析
给定一个字符串，统计其中回文子串的数目。子串是连续的一段字符，而不是子序列。
这里的「不同」是按位置区分而非按内容区分：只要起止下标不同就算作两个不同的子串，哪怕它们的字符完全一样。这一点直接决定了答案的量级——
"aaa"里三个单独的a要计三次，答案是 6 而不是去重后的 3。
约束信号在于字符串长度上限只有 1000 量级，这意味着 $O(n^2)$ 的时间是被允许的，不必去追求线性算法；同时也提醒 $O(n^2)$ 的额外空间虽然勉强能过，但如果能做到 $O(1)$ 空间会更好。
边界要点：长度为 1 的子串一定是回文，所以答案至少是 $n$；长度为 2 的子串是回文当且仅当两个字符相同；字符串本身可能整体就是回文；全部字符相同时回文子串数量达到最大值 $n(n+1)/2$。
解法：中心扩展
核心思路
枚举所有子串再逐个判断回文需要 $O(n^3)$。区间 DP 能降到 $O(n^2)$，但还要保存一张 $O(n^2)$ 的表。本题只统计数量，直接利用“回文从中心向两侧对称生长”的性质更简单：枚举中心，只要左右字符相同就扩一层并把答案加一。
中心有两类：
(i, i)覆盖奇数长度回文，(i, i + 1)覆盖偶数长度回文，共 $2n-1$ 个。每个回文子串都有唯一的中心和扩展半径，因此不会重算，也不会漏掉。扩展时的不变量是：进入下一轮前，上一轮的
[left + 1, right - 1]已经是回文；若本轮两端仍相等，[left, right]就是一个新的回文。第一次越界或失配后，更大的同中心区间不可能是回文，可以立即停止。这也给出了算法的正确性。
解题步骤
- 遍历每个下标
i，分别把(i, i)和(i, i + 1)当作奇、偶回文中心。- 从中心向两侧扩展；边界合法且字符相等时，当前区间就是一个新回文，计数加一。
- 左指针左移、右指针右移；越界或字符不同就结束当前中心的扩展。
- 累加所有中心的贡献并返回。
例如
"aaa"：三个单字符贡献 3，两个偶数中心得到两个"aa"，中间的奇数中心再得到一个"aaa"，总数为 6。
代码实现
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)$，只使用计数器和左右指针。
关键点总结
- 回文既可能以字符为中心，也可能以两个字符之间的空隙为中心。
- “中心 + 扩展半径”唯一确定一个回文子串，这是不重不漏的依据。
- 本题按下标区间计数，不按字符串内容去重。
- 与“最长回文子串”共用同一扩展模板：本题每次成功就计数，后者更新最长区间。
易错点总结
- 漏掉偶数中心：只扩展
(i, i)时，"aa"会得到 2 而不是 3。- 按内容去重：
"aaa"中三个位置上的"a"都要计数，答案是 6，不是 3。- 失配后继续向外扩：
"axbya"的内层x != y，即使外层a == a，整段也不是回文。- 先访问字符再检查边界：扩到
left = -1时会越界；循环条件必须先判左右边界。- 每个中心只计一次：同一中心可以产生多层回文，例如
"aaa"的中间中心同时产生"a"和"aaa"。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 5. 最长回文子串 | 中等 | 同一套中心扩展，扩展成功时记录区间而非计数 |
| LCR 020. 回文子串 | 中等 | 与本题完全同题，可直接复用同一份代码 |
| 516. 最长回文子序列 | 中等 | 对象是子序列，不连续因而无中心可扩，只能 dp |
| 131. 分割回文串 | 中等 | 回文判定只是子过程，主体是回溯枚举所有分割 |
| 214. 最短回文串 | 困难 | 求最长回文前缀，需借助 KMP 的前缀函数做到线性 |