LeetCode-Go 题解：647. Palindromic Substrings 回文子串计数与中心扩散法全解析
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
本文基于 LeetCode-Go 仓库中 647 题解文档 及其对应实现展开，围绕"统计字符串中全部回文子串数量"这一经典问题，详细拆解中心扩散（Center Expansion）算法的原理、Go 源码实现、复杂度分析与测试验证，并顺带对比同仓库 5. Longest Palindromic Substring 一题中的多种解法，帮助读者彻底掌握"以字符为轴、向两侧扩展"这一字符串回文处理的核心套路。读完本文，你将能独立写出可 100% 通过测试的countSubstrings实现，并理解其在 LeetCode 647 与 5 两题之间的迁移关系。
题目原文
Given a string, your task is to count how many palindromic substrings in this string.
The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
Example 1:
Input: "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c".Example 2:
Input: "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".Note:
- The input string length won't exceed 1000.
题目大意
给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
这句话是本题最容易踩坑的"陷阱"：例如输入"aaa"，虽然只有a一种字符，但三个位置的下标各不相同，因此单个字符的回文就有 3 个；再加上"aa"在[0,1]与[1,2]两处各算一个、"aaa"整体算一个，最终答案是 6，而不是"去重后"的 3。
解题思路：中心扩散法
原题解文档给出的核心思路非常凝练：暴力解法，从左往右扫一遍字符串，以每个字符做轴，用中心扩散法，依次遍历计数回文子串。
中心扩散法的本质是：任意一个回文子串都可以看作"以某个中心向左右两侧对称扩展"的结果。因此只要枚举出所有可能的中心，再对每个中心向两侧扩散并统计能扩散出多少个回文子串，累加后即为答案。
关键在于中心有两种形态：
| 中心形态 | 表示方式 | 对应回文长度 |
|---|---|---|
| 奇数长度回文 | 中心为单个字符s[i] | 1, 3, 5, … |
| 偶数长度回文 | 中心为两个相邻字符s[i]与s[i+1] | 2, 4, 6, … |
对于长度为n的字符串，奇偶两种中心加起来一共有2n - 1个（n个单字符中心 +n-1个双字符中心），枚举全部中心后逐个扩散，即可保证既不重也不漏地统计出所有回文子串。
为什么单个字符一定是回文？
在中心扩散的计数过程中，当left == right时，s[left] == s[right]恒成立，因此至少能扩散出长度为 1 的回文子串。这恰好对应了"每个单字符都是回文"这一事实，也是"abc"答案恰为 3 的原因。
源码实现深度解读
仓库中的实际实现位于 leetcode/0647.Palindromic-Substrings/647. Palindromic Substrings.go，与题解文档中的代码完全一致：
package leetcode func countSubstrings(s string) int { res := 0 for i := 0; i < len(s); i++ { res += countPalindrome(s, i, i) res += countPalindrome(s, i, i+1) } return res } func countPalindrome(s string, left, right int) int { res := 0 for left >= 0 && right < len(s) { if s[left] != s[right] { break } left-- right++ res++ } return res }这段代码的精妙之处可以逐层拆解：
外层循环：
for i := 0; i < len(s); i++从左到右枚举每个下标i。对每个i，同时调用两次countPalindrome：countPalindrome(s, i, i)：以s[i]为轴，扩散奇数长度回文；countPalindrome(s, i, i+1)：以s[i]与s[i+1]之间为轴，扩散偶数长度回文。
两次调用之和，就是"以位置 i 为左半边中心"能贡献的全部回文子串数量。需要特别注意的是，
i+1可能越界（当i == len(s)-1时，countPalindrome(s, i, i+1)的right初始即为len(s)），但由于扩散循环的终止条件right < len(s)在第一次判断时就为假，函数会直接返回 0，无需额外的越界防护——这一写法既简洁又安全，是值得借鉴的 Go 编码细节。内层扩散循环：
countPalindrome中，只要left >= 0 && right < len(s)且s[left] == s[right]，就说明以该中心能再向外扩一层，此时res++并继续left--, right++。一旦两侧字符不等或指针越界，立即break返回。每次成功扩散一格，就恰好代表找到一个新的回文子串。计数语义：对同一个中心，从长度为 1（或 2）开始，每扩散成功一次计数加 1，因此
countPalindrome返回的正是"以该中心为轴的所有回文子串数量"。
手动推演："abc"与"aaa"
以"abc"为例走一遍流程：
i=0：奇中心"a"扩散 1 次（res=1）；偶中心"ab"不相等（res=0）；i=1：奇中心"b"扩散 1 次（res=1）；偶中心"bc"不相等（res=0）；i=2：奇中心"c"扩散 1 次（res=1）；偶中心越界返回 0。
合计1+1+1 = 3，与官方示例一致。
再以"aaa"为例：
i=0：奇中心"a"得 1；偶中心"aa"得 1；i=1：奇中心"b"（即中间的a）扩散出"a"、"aaa"共 2；偶中心"aa"得 1；i=2：奇中心"c"（末尾的a）得 1；偶中心越界得 0。
合计2 + 3 + 1 = 6，与官方示例完全吻合：3 个单字符 + 2 个"aa"+ 1 个"aaa"。
复杂度分析
- 时间复杂度：O(n²)。外层循环枚举
2n-1个中心，最坏情况下（如全同字符"aaaa…"）每个中心都要扩散到字符串两端，扩散总长度为 O(n)，因此总复杂度为 O(n²)。题目约束输入长度不超过 1000，O(n²) 在 10⁶ 量级，可以轻松通过。 - 空间复杂度：O(1)。仅使用
res、left、right等常量级变量，不依赖与 n 相关的额外存储。这是中心扩散法相比动态规划（通常需要 O(n²) 的二维布尔数组）在空间上的显著优势。
测试验证与覆盖率
仓库为该题配套了完整的单元测试 647. Palindromic Substrings_test.go，采用本仓库统一的"para / ans"表驱动测试风格：
type question647 struct { para647 ans647 } type para647 struct { s string } type ans647 struct { one int } func Test_Problem647(t *testing.T) { qs := []question647{ { para647{"abc"}, ans647{3}, }, { para647{"aaa"}, ans647{6}, }, } // ... for _, q := range qs { _, p := q.ans647, q.para647 fmt.Printf("【input】:%v 【output】:%v\n", p, countSubstrings(p.s)) } }两个测试用例恰好对应官方给出的两组示例（"abc" → 3、"aaa" → 6），覆盖了奇数回文与偶数回文并存、同字符重复计数的场景。在仓库根目录执行 gotest.sh 中的测试命令即可验证：
go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...该命令一次性对所有leetcode包执行带覆盖率统计的测试，产出的coverage.txt用于覆盖率上报。读者也可以单独跑本题所在包的测试：
go test -v ./leetcode/0647.Palindromic-Substrings/ -run Test_Problem647从实现上看，countSubstrings与countPalindrome两个函数的全部分支（外层两次调用、内层相等/不等、指针越界）都会被测试覆盖，符合仓库"100% test coverage"的整体要求。
与同仓库其他回文题解的联系
中心扩散法在本仓库中并非孤例，它与 5. Longest Palindromic Substring 一题有着天然的迁移关系。查看 5. Longest Palindromic Substring 源码 可以发现，该题给出了四种解法：
- 解法三：中心扩散法（
longestPalindrome2）：同样枚举i, i与i, i+1两类中心并向外扩散，与本题的countSubstrings结构几乎一致，差别仅在于本题需要计数所有回文子串，而 5 题只需要记录最长的那一个； - 解法一：Manacher 算法（
longestPalindrome）：通过插入#辅助字符把偶数回文统一成奇数回文，用dp[i]数组记录回文半径，将时间复杂度优化到 O(n)； - 解法二：滑动窗口（
longestPalindrome1）与解法四：动态规划（longestPalindrome3）。
因此，647 与 5 可以看作"中心扩散法"的一对孪生题目：先学会 647 的计数扩散，再看 5 题的四种解法对比，就能理解同一套路在不同问题形态下的变体。如果读者追求更极致的性能，也可以基于 5 题的 Manacher 思路为本题设计 O(n) 解法——不过对于长度上限仅 1000 的本题而言，O(n²) 的中心扩散法已经是最简洁、最不易出错的答案。
总结
LeetCode 647 是"回文子串计数"的入门级经典题，核心考点有三个：
- 中心形态的完整性：必须同时枚举单字符中心（奇数回文）与双字符中心（偶数回文），漏掉任何一种都会导致答案偏小；
- 重复计数的正确性：题目明确"不同起止下标即视为不同子串"，即使字符相同也要分别计数；
- O(n²) 时间、O(1) 空间的平衡：相比 DP 的 O(n²) 空间，中心扩散在本题约束下是更优的工程选择。
本文对应的完整实现与测试均位于 leetcode/0647.Palindromic-Substrings 目录，其中 题解文档、核心实现 与 单元测试 三份文件相互印证，可直接作为学习与复盘的素材。
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
