LeetCode 5. Longest Palindromic SubstringLeetCode-Go 项目中四种 Go 解法深度剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本篇以 LeetCode-Go 仓库中 leetcode/0005.Longest-Palindromic-Substring 的官方题解文档为主体完整拆解「最长回文子串」这一经典面试题从题目约束出发依次讲解动态规划、中心扩散、滑动窗口、马拉车Manacher四种解法在 Go 中的实现细节、状态设计与复杂度分析并结合仓库内的源码与测试用例验证每种解法的正确性。读完本文你将掌握最长回文子串问题的完整解法脉络理解 Manacher 算法dp[i] min(maxRight-i, dp[2*center-i])这一核心递推背后的原理并能直接运行本仓库的测试代码验证结果。题目回顾约束与输入输出原文档给出了完整题目描述给定一个字符串s返回s中最长的回文子串。四个官方示例s babad→bababa同样是合法答案s cbbd→bbs a→as ac→a约束条件1 s.length 1000s仅由数字和英文字母大小写均可组成题目大意非常直接找到给定字符串中最长的回文子串。需要注意输出结果不唯一如示例 1只要返回其中一个合法最长回文子串即可。四种解法总览复杂度对比原文档指出此题解法众多本仓库代码实现了其中四种。先看整体复杂度对比解法对应函数时间复杂度空间复杂度核心思想解法一 Manacher马拉车longestPalindromeO(n)O(n)预处理 对称性复用解法二 滑动窗口longestPalindrome1O(n²)O(1)相同字符合并 中心扩散变体解法三 中心扩散longestPalindrome2O(n²)O(1)枚举奇偶两种轴心解法四 动态规划longestPalindrome3O(n²)O(n²)区间 DP 状态转移四种实现全部位于源码文件 5. Longest Palindromic Substring.go 中且全部通过 5. Longest Palindromic Substring_test.go 中的Test_Problem5测试用例验证。解法四动态规划O(n²) / O(n²)状态定义与转移方程定义dp[i][j]表示从字符串第i个字符到第j个字符这一段子串是否为回文串。由回文串的性质可知回文串去掉一头一尾相同字符后剩下的仍然是回文串。因此状态转移方程为dp[i][j] (s[i] s[j]) ((j-i 3) || dp[i1][j-1])其中需要特别处理两个边界情况j - i 1子串只有 2 个字符只需判断这 2 个字符是否相同j - i 2子串只有 3 个字符只需判断除去中心以外对称的 2 个字符是否相等。这两种情况由j-i 3统一覆盖——长度小于 3 的区间不需要依赖内部子区间。Go 实现解析仓库中longestPalindrome3的实现如下// 解法四 DP时间复杂度 O(n^2)空间复杂度 O(n^2) func longestPalindrome3(s string) string { res, dp : , make([][]bool, len(s)) for i : 0; i len(s); i { dp[i] make([]bool, len(s)) } for i : len(s) - 1; i 0; i-- { for j : i; j len(s); j { dp[i][j] (s[i] s[j]) ((j-i 3) || dp[i1][j-1]) if dp[i][j] (res || j-i1 len(res)) { res s[i : j1] } } } return res }实现要点遍历方向外层i从len(s)-1递减到 0因为dp[i][j]依赖dp[i1][j-1]必须保证内层区间先被计算因此需要从右下角向左上角推进j 的起点j从i开始只计算j i的区间无需初始化对角线和无效区域答案维护每发现一个dp[i][j]为真就与当前res比较长度最终返回最长回文子串。原文档明确指出此方法的时间复杂度 O(n²)、空间复杂度 O(n²)——空间开销主要来自dp二维布尔表这是后续几种解法优化的起点。解法三中心扩散法O(n²) / O(1)思路找到轴心向两侧扩散动态规划将任意起始、终止范围内的字符串都判断了一遍其实没有这个必要——如果不是最长回文串无需判断并保存结果。因此动态规划在空间复杂度上仍有优化空间。判断回文有一个核心问题是找到「轴心」如果回文串长度是偶数轴心是中心虚拟的位于两个字符之间如果长度是奇数轴心正好是正中心的那个字母。中心扩散法的思想是枚举每个轴心的位置然后做两次假设假设最长回文串是偶数以虚拟中心往两边扩散假设最长回文串是奇数以正中心的字符往两边扩散。扩散的过程就是对称判断两边字符是否相等的过程。该方法时间复杂度与动态规划相同O(n²)但空间复杂度降低到 O(1)。Go 实现解析仓库中longestPalindrome2与辅助函数maxPalindrome实现如下// 解法三 中心扩散法时间复杂度 O(n^2)空间复杂度 O(1) func longestPalindrome2(s string) string { res : for i : 0; i len(s); i { res maxPalindrome(s, i, i, res) res maxPalindrome(s, i, i1, res) } return res } func maxPalindrome(s string, i, j int, res string) string { sub : for i 0 j len(s) s[i] s[j] { sub s[i : j1] i-- j } if len(res) len(sub) { return sub } return res }实现要点对每个下标i分别以(i, i)奇数中心和(i, i1)偶数中心为轴心调用maxPalindromemaxPalindrome从中心向两边对称扩展条件不满足越界或字符不等时退出返回值与当前最优res比较长度始终维护最长结果。这种写法没有额外的数组空间复杂度 O(1)是面试中最容易现场写出的解法之一。解法二滑动窗口O(n²) / O(1)思路中心扩散的另一种写法原文档指出滑动窗口写法本质上是中心扩散法换了种写法。中心扩散是依次枚举每一个轴心滑动窗口方法稍作优化——有些轴心两边字符不相等下次就不会再枚举这些不可能形成回文子串的轴心。但这点优化并未改变时间复杂度仍是 O(n²)空间复杂度 O(1)。Go 实现解析仓库中longestPalindrome1实现如下// 解法二 滑动窗口时间复杂度 O(n^2)空间复杂度 O(1) func longestPalindrome1(s string) string { if len(s) 0 { return } left, right, pl, pr : 0, -1, 0, 0 for left len(s) { // 移动到相同字母的最右边如果有相同字母 for right1 len(s) s[left] s[right1] { right } // 找到回文的边界 for left-1 0 right1 len(s) s[left-1] s[right1] { left-- right } if right-left pr-pl { pl, pr left, right } // 重置到下一次寻找回文的中心 left (leftright)/2 1 right left } return s[pl : pr1] }实现要点合并相同字符第一个内层循环先把right推到与s[left]相同的最右位置一次性跳过连续的相同字母——这对应「轴心可以是一段相同字符的区间」的观察向外扩散第二个内层循环从该区间的两侧对称扩展找出以该连续区间为中心的最长回文记录并重置用pl、pr记录全局最长区间结束后把left重置为(leftright)/2 1即当前回文中心右侧的下一个位置right同步重置保证不重复枚举已被判定的轴心区间边界处理对空串直接返回此分支在测试用例中也被覆盖。这种写法通过「相同字符区间」合并优化了枚举粒度是中心扩散思想的一种工程化变体。解法一Manacher 马拉车算法O(n) / O(n)为什么要做预处理统一奇偶原文档指出中心扩散法有 2 处重复判断每次都往两边扩散不同中心扩散多次实际上有很多重复判断的字符——能否不重复判断中心能否跳跃选择而不是每次都枚举——是否可以利用前一次的信息跳跃选择下一次的中心马拉车算法正是针对这两处重复判断做了优化增加一个辅助数组将时间复杂度从 O(n²) 优化到 O(n)以空间换时间空间复杂度增加到 O(n)。预处理向字符串的头尾以及每两个字符中间添加一个特殊字符#。例如字符串aaba处理后会变成#a#a#b#a#原先长度为偶数的回文串aa会变成奇数长度的#a#a#原先长度为奇数的回文串aba会变成仍为奇数长度的#a#b#a#。经过预处理后所有回文串都统一为奇数长度从而只需处理一种中心情况。一个值得注意的细节原文档特别强调这里的特殊字符不需要是没有出现过的字母任意字符都可以作为特殊字符。原因在于当只考虑奇数长度的回文串时每次比较的两个字符奇偶性一定相同所以原字符串中的字符不会与插入的特殊字符互相比较不会因此产生问题。另一个关键结论预处理以后以某个中心扩散的步数和实际字符串长度相等。因为半径里包含了插入的特殊字符又由于左右对称的性质扩散半径就等于原来回文子串的长度。核心递推dp[i] min(maxRight-i, dp[2*center-i])原文档给出了核心部分的推理。定义下一次要扩散的中心下标为i如果i比maxRight大严格说是i maxRight无法利用已有信息只能继续中心扩散如果i比maxRight小此时i落在已知回文区间[center - dp[center], center dp[center]]内可借助与i关于center对称的镜像点mirror 2*center - i的已知半径来初始化dp[i]。将上述情况总结起来就是核心公式dp[i] min(maxRight-i, dp[2*center-i])其中mirror相对于center与i中心对称下标为2*center-i。更新完dp[i]以后进行中心扩散扩散后动态维护最长回文串并相应更新center、maxRight同时记录原始字符串中的起始位置begin和最大半径maxLen。Go 实现解析仓库中longestPalindromeManacher 主函数与辅助函数min实现如下// 解法一 Manachers algorithm时间复杂度 O(n)空间复杂度 O(n) func longestPalindrome(s string) string { if len(s) 2 { return s } newS : make([]rune, 0) newS append(newS, #) for _, c : range s { newS append(newS, c) newS append(newS, #) } // dp[i]: 以预处理字符串下标 i 为中心的回文半径(奇数长度时不包括中心) // maxRight: 通过中心扩散的方式能够扩散的最右边的下标 // center: 与 maxRight 对应的中心字符的下标 // maxLen: 记录最长回文串的半径 // begin: 记录最长回文串在起始串 s 中的起始下标 dp, maxRight, center, maxLen, begin : make([]int, len(newS)), 0, 0, 1, 0 for i : 0; i len(newS); i { if i maxRight { // 这一行代码是 Manacher 算法的关键所在 dp[i] min(maxRight-i, dp[2*center-i]) } // 中心扩散法更新 dp[i] left, right : i-(1dp[i]), i(1dp[i]) for left 0 right len(newS) newS[left] newS[right] { dp[i] left-- right } // 更新 maxRight它是遍历过的 i 的 i dp[i] 的最大者 if idp[i] maxRight { maxRight i dp[i] center i } // 记录最长回文子串的长度和相应它在原始字符串中的起点 if dp[i] maxLen { maxLen dp[i] begin (i - maxLen) / 2 // 这里要除以 2 因为有我们插入的辅助字符 # } } return s[begin : beginmaxLen] } func min(x, y int) int { if x y { return x } return y }分步解读预处理用[]rune构建#与原字符交替的newS。注意使用rune切片而非byte可正确处理多字节字符避免下标错位变量语义dp[i]为以i为中心的回文半径奇数长度时不含中心本身maxRight是已遍历过中心中能扩散到的最右下标center是与maxRight对应的中心maxLen、begin记录最优答案对称性初始化if i maxRight时用min(maxRight-i, dp[2*center-i])直接给dp[i]一个下界这是整个算法不重复判断的关键一行中心扩散补全left, right : i-(1dp[i]), i(1dp[i])从已确认的半径外一格外开始比对循环内对称字符相等则dp[i]并继续外扩动态维护每次扩散完若idp[i] maxRight则更新maxRight与center若dp[i] maxLen则更新maxLen和begin坐标还原begin (i - maxLen) / 2需要除以 2因为预处理字符串中插入了辅助字符#最后返回s[begin : beginmaxLen]即为原始字符串中的最长回文子串。该解法时间 O(n)每个字符的扩散总次数受maxRight单调推进约束、空间 O(n)dp数组是本题的最优解也是四种解法中最复杂的。测试验证四种解法如何被同时验证本仓库对每道题都配有独立的_test.go测试文件。5. Longest Palindromic Substring_test.go 中的Test_Problem5定义了如下测试用例输入s期望输出babadbabcbbdbbaaacaaaaa一段 200 字符的长字符串与输入完全相同整个串本身即为回文测试用例覆盖了奇数回文、偶数回文、单字符、双字符、空串、以及整串回文最长边界等典型场景。值得关注的是用例组织方式每一条用例的答案都被同时传入四个函数并打印对比fmt.Printf(【input】:%v 【output】:%v %v %v %v\n, p, longestPalindrome(p.s), longestPalindrome1(p.s), longestPalindrome2(p.s), longestPalindrome3(p.s))这意味着一组测试输入同时校验 Manacher、滑动窗口、中心扩散、DP 四种实现的输出是否一致任何一版实现回归出错都会被立即发现。从代码结构看测试以fmt.Printf打印四种解法输出供人工比对仓库根目录的 gotest.sh 脚本则统一通过go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...对整个leetcode包生成覆盖率报告与本仓库「100% test coverage」的目标一致详见 README.md。若要在本地验证本题可以进入仓库根目录执行go test -v -run Test_Problem5 ./leetcode/0005.Longest-Palindromic-Substring/四种解法对比总结与选型建议从原文档与源码实现可以提炼出如下选型建议面试首推中心扩散法解法三。代码最短、思路直观、空间 O(1)易于在面试中现场推导和书写需要最优解Manacher 算法解法一。当n很大如本仓库测试中长达 200 字符的回文串且对时间复杂度敏感时O(n) 线性复杂度是唯一选择但实现细节多、不易一次写对适合作为进阶知识点掌握理解 DP 基础动态规划解法四虽空间开销大但状态转移方程是理解回文子串结构的最佳入门也是很多区间 DP 问题的通用模板工程化变体滑动窗口解法二通过合并相同字符区间减少枚举展示了对中心扩散的优化思路空间同样 O(1)。这四种解法完整覆盖了「从朴素到最优」的演进路径是理解回文串类问题的绝佳范例。读者可对照仓库中的 题解文档、源码 与 测试用例 三者联动研读形成完整的「题目 → 思路 → 实现 → 验证」闭环。【免费下载链接】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 5. Longest Palindromic Substring：LeetCode-Go 项目中四种 Go 解法深度剖析
LeetCode 5. Longest Palindromic SubstringLeetCode-Go 项目中四种 Go 解法深度剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本篇以 LeetCode-Go 仓库中 leetcode/0005.Longest-Palindromic-Substring 的官方题解文档为主体完整拆解「最长回文子串」这一经典面试题从题目约束出发依次讲解动态规划、中心扩散、滑动窗口、马拉车Manacher四种解法在 Go 中的实现细节、状态设计与复杂度分析并结合仓库内的源码与测试用例验证每种解法的正确性。读完本文你将掌握最长回文子串问题的完整解法脉络理解 Manacher 算法dp[i] min(maxRight-i, dp[2*center-i])这一核心递推背后的原理并能直接运行本仓库的测试代码验证结果。题目回顾约束与输入输出原文档给出了完整题目描述给定一个字符串s返回s中最长的回文子串。四个官方示例s babad→bababa同样是合法答案s cbbd→bbs a→as ac→a约束条件1 s.length 1000s仅由数字和英文字母大小写均可组成题目大意非常直接找到给定字符串中最长的回文子串。需要注意输出结果不唯一如示例 1只要返回其中一个合法最长回文子串即可。四种解法总览复杂度对比原文档指出此题解法众多本仓库代码实现了其中四种。先看整体复杂度对比解法对应函数时间复杂度空间复杂度核心思想解法一 Manacher马拉车longestPalindromeO(n)O(n)预处理 对称性复用解法二 滑动窗口longestPalindrome1O(n²)O(1)相同字符合并 中心扩散变体解法三 中心扩散longestPalindrome2O(n²)O(1)枚举奇偶两种轴心解法四 动态规划longestPalindrome3O(n²)O(n²)区间 DP 状态转移四种实现全部位于源码文件 5. Longest Palindromic Substring.go 中且全部通过 5. Longest Palindromic Substring_test.go 中的Test_Problem5测试用例验证。解法四动态规划O(n²) / O(n²)状态定义与转移方程定义dp[i][j]表示从字符串第i个字符到第j个字符这一段子串是否为回文串。由回文串的性质可知回文串去掉一头一尾相同字符后剩下的仍然是回文串。因此状态转移方程为dp[i][j] (s[i] s[j]) ((j-i 3) || dp[i1][j-1])其中需要特别处理两个边界情况j - i 1子串只有 2 个字符只需判断这 2 个字符是否相同j - i 2子串只有 3 个字符只需判断除去中心以外对称的 2 个字符是否相等。这两种情况由j-i 3统一覆盖——长度小于 3 的区间不需要依赖内部子区间。Go 实现解析仓库中longestPalindrome3的实现如下// 解法四 DP时间复杂度 O(n^2)空间复杂度 O(n^2) func longestPalindrome3(s string) string { res, dp : , make([][]bool, len(s)) for i : 0; i len(s); i { dp[i] make([]bool, len(s)) } for i : len(s) - 1; i 0; i-- { for j : i; j len(s); j { dp[i][j] (s[i] s[j]) ((j-i 3) || dp[i1][j-1]) if dp[i][j] (res || j-i1 len(res)) { res s[i : j1] } } } return res }实现要点遍历方向外层i从len(s)-1递减到 0因为dp[i][j]依赖dp[i1][j-1]必须保证内层区间先被计算因此需要从右下角向左上角推进j 的起点j从i开始只计算j i的区间无需初始化对角线和无效区域答案维护每发现一个dp[i][j]为真就与当前res比较长度最终返回最长回文子串。原文档明确指出此方法的时间复杂度 O(n²)、空间复杂度 O(n²)——空间开销主要来自dp二维布尔表这是后续几种解法优化的起点。解法三中心扩散法O(n²) / O(1)思路找到轴心向两侧扩散动态规划将任意起始、终止范围内的字符串都判断了一遍其实没有这个必要——如果不是最长回文串无需判断并保存结果。因此动态规划在空间复杂度上仍有优化空间。判断回文有一个核心问题是找到「轴心」如果回文串长度是偶数轴心是中心虚拟的位于两个字符之间如果长度是奇数轴心正好是正中心的那个字母。中心扩散法的思想是枚举每个轴心的位置然后做两次假设假设最长回文串是偶数以虚拟中心往两边扩散假设最长回文串是奇数以正中心的字符往两边扩散。扩散的过程就是对称判断两边字符是否相等的过程。该方法时间复杂度与动态规划相同O(n²)但空间复杂度降低到 O(1)。Go 实现解析仓库中longestPalindrome2与辅助函数maxPalindrome实现如下// 解法三 中心扩散法时间复杂度 O(n^2)空间复杂度 O(1) func longestPalindrome2(s string) string { res : for i : 0; i len(s); i { res maxPalindrome(s, i, i, res) res maxPalindrome(s, i, i1, res) } return res } func maxPalindrome(s string, i, j int, res string) string { sub : for i 0 j len(s) s[i] s[j] { sub s[i : j1] i-- j } if len(res) len(sub) { return sub } return res }实现要点对每个下标i分别以(i, i)奇数中心和(i, i1)偶数中心为轴心调用maxPalindromemaxPalindrome从中心向两边对称扩展条件不满足越界或字符不等时退出返回值与当前最优res比较长度始终维护最长结果。这种写法没有额外的数组空间复杂度 O(1)是面试中最容易现场写出的解法之一。解法二滑动窗口O(n²) / O(1)思路中心扩散的另一种写法原文档指出滑动窗口写法本质上是中心扩散法换了种写法。中心扩散是依次枚举每一个轴心滑动窗口方法稍作优化——有些轴心两边字符不相等下次就不会再枚举这些不可能形成回文子串的轴心。但这点优化并未改变时间复杂度仍是 O(n²)空间复杂度 O(1)。Go 实现解析仓库中longestPalindrome1实现如下// 解法二 滑动窗口时间复杂度 O(n^2)空间复杂度 O(1) func longestPalindrome1(s string) string { if len(s) 0 { return } left, right, pl, pr : 0, -1, 0, 0 for left len(s) { // 移动到相同字母的最右边如果有相同字母 for right1 len(s) s[left] s[right1] { right } // 找到回文的边界 for left-1 0 right1 len(s) s[left-1] s[right1] { left-- right } if right-left pr-pl { pl, pr left, right } // 重置到下一次寻找回文的中心 left (leftright)/2 1 right left } return s[pl : pr1] }实现要点合并相同字符第一个内层循环先把right推到与s[left]相同的最右位置一次性跳过连续的相同字母——这对应「轴心可以是一段相同字符的区间」的观察向外扩散第二个内层循环从该区间的两侧对称扩展找出以该连续区间为中心的最长回文记录并重置用pl、pr记录全局最长区间结束后把left重置为(leftright)/2 1即当前回文中心右侧的下一个位置right同步重置保证不重复枚举已被判定的轴心区间边界处理对空串直接返回此分支在测试用例中也被覆盖。这种写法通过「相同字符区间」合并优化了枚举粒度是中心扩散思想的一种工程化变体。解法一Manacher 马拉车算法O(n) / O(n)为什么要做预处理统一奇偶原文档指出中心扩散法有 2 处重复判断每次都往两边扩散不同中心扩散多次实际上有很多重复判断的字符——能否不重复判断中心能否跳跃选择而不是每次都枚举——是否可以利用前一次的信息跳跃选择下一次的中心马拉车算法正是针对这两处重复判断做了优化增加一个辅助数组将时间复杂度从 O(n²) 优化到 O(n)以空间换时间空间复杂度增加到 O(n)。预处理向字符串的头尾以及每两个字符中间添加一个特殊字符#。例如字符串aaba处理后会变成#a#a#b#a#原先长度为偶数的回文串aa会变成奇数长度的#a#a#原先长度为奇数的回文串aba会变成仍为奇数长度的#a#b#a#。经过预处理后所有回文串都统一为奇数长度从而只需处理一种中心情况。一个值得注意的细节原文档特别强调这里的特殊字符不需要是没有出现过的字母任意字符都可以作为特殊字符。原因在于当只考虑奇数长度的回文串时每次比较的两个字符奇偶性一定相同所以原字符串中的字符不会与插入的特殊字符互相比较不会因此产生问题。另一个关键结论预处理以后以某个中心扩散的步数和实际字符串长度相等。因为半径里包含了插入的特殊字符又由于左右对称的性质扩散半径就等于原来回文子串的长度。核心递推dp[i] min(maxRight-i, dp[2*center-i])原文档给出了核心部分的推理。定义下一次要扩散的中心下标为i如果i比maxRight大严格说是i maxRight无法利用已有信息只能继续中心扩散如果i比maxRight小此时i落在已知回文区间[center - dp[center], center dp[center]]内可借助与i关于center对称的镜像点mirror 2*center - i的已知半径来初始化dp[i]。将上述情况总结起来就是核心公式dp[i] min(maxRight-i, dp[2*center-i])其中mirror相对于center与i中心对称下标为2*center-i。更新完dp[i]以后进行中心扩散扩散后动态维护最长回文串并相应更新center、maxRight同时记录原始字符串中的起始位置begin和最大半径maxLen。Go 实现解析仓库中longestPalindromeManacher 主函数与辅助函数min实现如下// 解法一 Manachers algorithm时间复杂度 O(n)空间复杂度 O(n) func longestPalindrome(s string) string { if len(s) 2 { return s } newS : make([]rune, 0) newS append(newS, #) for _, c : range s { newS append(newS, c) newS append(newS, #) } // dp[i]: 以预处理字符串下标 i 为中心的回文半径(奇数长度时不包括中心) // maxRight: 通过中心扩散的方式能够扩散的最右边的下标 // center: 与 maxRight 对应的中心字符的下标 // maxLen: 记录最长回文串的半径 // begin: 记录最长回文串在起始串 s 中的起始下标 dp, maxRight, center, maxLen, begin : make([]int, len(newS)), 0, 0, 1, 0 for i : 0; i len(newS); i { if i maxRight { // 这一行代码是 Manacher 算法的关键所在 dp[i] min(maxRight-i, dp[2*center-i]) } // 中心扩散法更新 dp[i] left, right : i-(1dp[i]), i(1dp[i]) for left 0 right len(newS) newS[left] newS[right] { dp[i] left-- right } // 更新 maxRight它是遍历过的 i 的 i dp[i] 的最大者 if idp[i] maxRight { maxRight i dp[i] center i } // 记录最长回文子串的长度和相应它在原始字符串中的起点 if dp[i] maxLen { maxLen dp[i] begin (i - maxLen) / 2 // 这里要除以 2 因为有我们插入的辅助字符 # } } return s[begin : beginmaxLen] } func min(x, y int) int { if x y { return x } return y }分步解读预处理用[]rune构建#与原字符交替的newS。注意使用rune切片而非byte可正确处理多字节字符避免下标错位变量语义dp[i]为以i为中心的回文半径奇数长度时不含中心本身maxRight是已遍历过中心中能扩散到的最右下标center是与maxRight对应的中心maxLen、begin记录最优答案对称性初始化if i maxRight时用min(maxRight-i, dp[2*center-i])直接给dp[i]一个下界这是整个算法不重复判断的关键一行中心扩散补全left, right : i-(1dp[i]), i(1dp[i])从已确认的半径外一格外开始比对循环内对称字符相等则dp[i]并继续外扩动态维护每次扩散完若idp[i] maxRight则更新maxRight与center若dp[i] maxLen则更新maxLen和begin坐标还原begin (i - maxLen) / 2需要除以 2因为预处理字符串中插入了辅助字符#最后返回s[begin : beginmaxLen]即为原始字符串中的最长回文子串。该解法时间 O(n)每个字符的扩散总次数受maxRight单调推进约束、空间 O(n)dp数组是本题的最优解也是四种解法中最复杂的。测试验证四种解法如何被同时验证本仓库对每道题都配有独立的_test.go测试文件。5. Longest Palindromic Substring_test.go 中的Test_Problem5定义了如下测试用例输入s期望输出babadbabcbbdbbaaacaaaaa一段 200 字符的长字符串与输入完全相同整个串本身即为回文测试用例覆盖了奇数回文、偶数回文、单字符、双字符、空串、以及整串回文最长边界等典型场景。值得关注的是用例组织方式每一条用例的答案都被同时传入四个函数并打印对比fmt.Printf(【input】:%v 【output】:%v %v %v %v\n, p, longestPalindrome(p.s), longestPalindrome1(p.s), longestPalindrome2(p.s), longestPalindrome3(p.s))这意味着一组测试输入同时校验 Manacher、滑动窗口、中心扩散、DP 四种实现的输出是否一致任何一版实现回归出错都会被立即发现。从代码结构看测试以fmt.Printf打印四种解法输出供人工比对仓库根目录的 gotest.sh 脚本则统一通过go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...对整个leetcode包生成覆盖率报告与本仓库「100% test coverage」的目标一致详见 README.md。若要在本地验证本题可以进入仓库根目录执行go test -v -run Test_Problem5 ./leetcode/0005.Longest-Palindromic-Substring/四种解法对比总结与选型建议从原文档与源码实现可以提炼出如下选型建议面试首推中心扩散法解法三。代码最短、思路直观、空间 O(1)易于在面试中现场推导和书写需要最优解Manacher 算法解法一。当n很大如本仓库测试中长达 200 字符的回文串且对时间复杂度敏感时O(n) 线性复杂度是唯一选择但实现细节多、不易一次写对适合作为进阶知识点掌握理解 DP 基础动态规划解法四虽空间开销大但状态转移方程是理解回文子串结构的最佳入门也是很多区间 DP 问题的通用模板工程化变体滑动窗口解法二通过合并相同字符区间减少枚举展示了对中心扩散的优化思路空间同样 O(1)。这四种解法完整覆盖了「从朴素到最优」的演进路径是理解回文串类问题的绝佳范例。读者可对照仓库中的 题解文档、源码 与 测试用例 三者联动研读形成完整的「题目 → 思路 → 实现 → 验证」闭环。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考