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 wont exceed 1000.题目大意给定一个字符串你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。这句话是本题最容易踩坑的陷阱例如输入aaa虽然只有a一种字符但三个位置的下标各不相同因此单个字符的回文就有 3 个再加上aa在[0,1]与[1,2]两处各算一个、aaa整体算一个最终答案是 6而不是去重后的 3。解题思路中心扩散法原题解文档给出的核心思路非常凝练暴力解法从左往右扫一遍字符串以每个字符做轴用中心扩散法依次遍历计数回文子串。中心扩散法的本质是任意一个回文子串都可以看作以某个中心向左右两侧对称扩展的结果。因此只要枚举出所有可能的中心再对每个中心向两侧扩散并统计能扩散出多少个回文子串累加后即为答案。关键在于中心有两种形态中心形态表示方式对应回文长度奇数长度回文中心为单个字符s[i]1, 3, 5, …偶数长度回文中心为两个相邻字符s[i]与s[i1]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, i1) } 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同时调用两次countPalindromecountPalindrome(s, i, i)以s[i]为轴扩散奇数长度回文countPalindrome(s, i, i1)以s[i]与s[i1]之间为轴扩散偶数长度回文。两次调用之和就是以位置 i 为左半边中心能贡献的全部回文子串数量。需要特别注意的是i1可能越界当i len(s)-1时countPalindrome(s, i, i1)的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为例走一遍流程i0奇中心a扩散 1 次res1偶中心ab不相等res0i1奇中心b扩散 1 次res1偶中心bc不相等res0i2奇中心c扩散 1 次res1偶中心越界返回 0。合计111 3与官方示例一致。再以aaa为例i0奇中心a得 1偶中心aa得 1i1奇中心b即中间的a扩散出a、aaa共 2偶中心aa得 1i2奇中心c末尾的a得 1偶中心越界得 0。合计2 3 1 6与官方示例完全吻合3 个单字符 2 个aa 1 个aaa。复杂度分析时间复杂度O(n²)。外层循环枚举2n-1个中心最坏情况下如全同字符aaaa…每个中心都要扩散到字符串两端扩散总长度为 O(n)因此总复杂度为 O(n²)。题目约束输入长度不超过 1000O(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 -covermodeatomic -coverprofilecoverage.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, i1两类中心并向外扩散与本题的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），仅供参考 LeetCode-Go 题解：647. Palindromic Substrings 回文子串计数与中心扩散法全解析
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 wont exceed 1000.题目大意给定一个字符串你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串即使是由相同的字符组成也会被视作不同的子串。这句话是本题最容易踩坑的陷阱例如输入aaa虽然只有a一种字符但三个位置的下标各不相同因此单个字符的回文就有 3 个再加上aa在[0,1]与[1,2]两处各算一个、aaa整体算一个最终答案是 6而不是去重后的 3。解题思路中心扩散法原题解文档给出的核心思路非常凝练暴力解法从左往右扫一遍字符串以每个字符做轴用中心扩散法依次遍历计数回文子串。中心扩散法的本质是任意一个回文子串都可以看作以某个中心向左右两侧对称扩展的结果。因此只要枚举出所有可能的中心再对每个中心向两侧扩散并统计能扩散出多少个回文子串累加后即为答案。关键在于中心有两种形态中心形态表示方式对应回文长度奇数长度回文中心为单个字符s[i]1, 3, 5, …偶数长度回文中心为两个相邻字符s[i]与s[i1]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, i1) } 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同时调用两次countPalindromecountPalindrome(s, i, i)以s[i]为轴扩散奇数长度回文countPalindrome(s, i, i1)以s[i]与s[i1]之间为轴扩散偶数长度回文。两次调用之和就是以位置 i 为左半边中心能贡献的全部回文子串数量。需要特别注意的是i1可能越界当i len(s)-1时countPalindrome(s, i, i1)的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为例走一遍流程i0奇中心a扩散 1 次res1偶中心ab不相等res0i1奇中心b扩散 1 次res1偶中心bc不相等res0i2奇中心c扩散 1 次res1偶中心越界返回 0。合计111 3与官方示例一致。再以aaa为例i0奇中心a得 1偶中心aa得 1i1奇中心b即中间的a扩散出a、aaa共 2偶中心aa得 1i2奇中心c末尾的a得 1偶中心越界得 0。合计2 3 1 6与官方示例完全吻合3 个单字符 2 个aa 1 个aaa。复杂度分析时间复杂度O(n²)。外层循环枚举2n-1个中心最坏情况下如全同字符aaaa…每个中心都要扩散到字符串两端扩散总长度为 O(n)因此总复杂度为 O(n²)。题目约束输入长度不超过 1000O(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 -covermodeatomic -coverprofilecoverage.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, i1两类中心并向外扩散与本题的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），仅供参考