1. 从一道高频面试题说起最长回文子串几乎每个刷过LeetCode的人都见过它第5题难度中等。但你要是真去统计一下这道题在面试里出现的频率绝对能排进字符串类题目的前三。我见过不少候选人能把动态规划的代码背得滚瓜烂熟但被问到“为什么要从长度短的子串开始遍历”就卡住了也有人写出了中心扩展却说不清为什么时间复杂度是O(n²)。这恰恰说明很多人只是记住了代码并没有真正理解这个问题的本质。这篇东西不是单纯给你讲题解我想把这道题彻底拆开从暴力解法一步步推导到最优解把每种思路的动机、细节、坑都讲透。无论你是准备面试、刷竞赛还是想系统理解字符串处理这篇文章都值得看完。我把话放在前面最长回文子串不是一道需要死记硬背的题它是一把理解动态规划、双指针和字符串优化的钥匙。先说一个很多人问过我的问题最长回文子串和最长回文子序列有什么区别子串要求连续子序列不要求连续。比如字符串“abca”它的最长回文子串是“a”或“b”或“c”长度1但最长回文子序列是“aba”或“aca”长度3。很多初学者在这里就绕晕了所以先把这个边界划清楚后面的讨论才不跑偏。2. 暴力法最容易想到也最容易超时2.1 暴力法到底在枚举什么暴力法的思路非常直白枚举所有可能的子串检查每一个子串是不是回文记录其中最长的那个。假设字符串长度为n子串总数是O(n²)检查一个子串是否是回文需要O(n)的时间所以总复杂度是O(n³)。用代码写出来就是def longestPalindrome(s: str) - str: n len(s) if n 2: return s max_len 1 begin 0 for i in range(n - 1): for j in range(i 1, n): if j - i 1 max_len and isPalindrome(s, i, j): max_len j - i 1 begin i return s[begin:begin max_len] def isPalindrome(s: str, left: int, right: int) - bool: while left right: if s[left] ! s[right]: return False left 1 right - 1 return True这段代码逻辑本身没错但在LeetCode上跑基本就是超时的命。n稍微大一点比如1000三层循环就是10亿次操作放在任何语言里都扛不住。2.2 为什么暴力法依然值得分析我不建议你直接跳过暴力法。原因有两个第一暴力法是所有优化方案的“基准线”。动态规划、中心扩展、Manacher算法本质上都是在做同一件事减少“枚举子串”和“判断回文”这两部分的开销。你只有清楚暴力法慢在哪里才能理解后续每一点优化到底优化了什么。第二暴力法提供了一个最简单的验证方法。我在实际调试优化算法时经常写一个暴力版的结果作为“标准答案”拿优化算法的输出跟它对比。特别是Manacher这种容易出边界bug的算法没有暴力法做参照错了都不知道错在哪。3. 动态规划用空间换时间的经典思路3.1 状态定义与状态转移动态规划的核心是把“判断一个子串是不是回文”这件事拆成更小的子问题。定义一个二维布尔数组dp[i][j]表示子串s[i:j1]i和j是闭区间是否是回文。那么状态转移方程是dp[i][j] (s[i] s[j]) and dp[i1][j-1]这个方程的理解很关键一个子串是回文必须同时满足两个条件——首尾字符相等并且去掉首尾之后剩下的部分也是回文。举个例子判断“ababa”是否为回文首尾都是‘a’相等再看“bab”首尾都是‘b’相等再看“a”单个字符是回文。一层层往里剥这就是动态规划的思维。3.2 为什么必须按长度遍历这几乎是这道题面试时必问的一个点。先看错误示范按i从小到大、j从大到小或从小到大遍历。比如先算dp[0][4]需要用到dp[1][3]但此时dp[1][3]还没算出来拿到的就是初始值false结果自然错了。正确做法是按子串长度从小到大遍历先算所有长度为1的子串再算所有长度为2的然后是长度为3的……这样当计算dp[i][j]时dp[i1][j-1]对应的子串长度为j-i-1一定比当前子串长度小必然已经计算过。def longestPalindrome(s: str) - str: n len(s) if n 2: return s dp [[False] * n for _ in range(n)] max_len 1 begin 0 # 长度为1的子串都是回文 for i in range(n): dp[i][i] True # 按长度递增遍历 for length in range(2, n 1): for i in range(n - length 1): j i length - 1 if s[i] ! s[j]: dp[i][j] False else: if length 2: dp[i][j] True else: dp[i][j] dp[i 1][j - 1] if dp[i][j] and length max_len: max_len length begin i return s[begin:begin max_len]3.3 动态规划的两个隐藏重点说两个容易忽略的细节。第一个是长度为2的边界处理。当s[i]s[j]且length2时dp[i1][j-1]实际上是dp[i1][i]这在我们的表中没有被初始化直接访问会得到false。所以必须单独处理长度为2且首尾相等就是回文。第二个是空间复杂度的代价。dp表是n×n的布尔矩阵空间复杂度O(n²)。当n5000时就是2500万个布尔值虽然Python的False/True是单例但二维列表本身的开销也不小。这也是为什么实际工程中动态规划不是首选——它虽然把时间复杂度降到了O(n²)但空间开销太大。有人会问能不能把dp表压缩成一维答案是不能简单地滚动数组因为dp[i][j]依赖的是dp[i1][j-1]在二维表里是“左下角”的值。如果你按长度遍历每一层的计算会跨行访问滚动数组没法保证被依赖的值不被覆盖。这也是动态规划解法的一个天然局限。4. 中心扩展常数级优化的胜利4.1 中心扩展的基本思路动态规划的O(n²)时间和O(n²)空间其实还有优化空间。换个角度想回文串的本质是什么是“围绕中心对称”。那与其枚举子串再判断不如直接枚举“中心”然后向两边扩展直到不能扩展为止。这个思路看起来很简单但它避开了动态规划最耗内存的dp表空间复杂度直接降到O(1)时间复杂度依然是O(n²)——因为枚举中心是O(n)的每个中心最多扩展O(n)次。这里有个容易踩坑的地方回文中心有两种。奇数长度的回文中心是单个字符偶数长度的回文中心是两个字符之间的空隙。比如“aba”的中心是‘b’“abba”的中心是“bb”中间。所以枚举中心时要分别处理这两种情况。def longestPalindrome(s: str) - str: n len(s) if n 2: return s max_len 1 begin 0 for center in range(n): # 奇数长度中心是center left, right center, center while left 0 and right n and s[left] s[right]: left - 1 right 1 # 扩展结束后回文范围是[left1, right-1] length right - left - 1 if length max_len: max_len length begin left 1 # 偶数长度中心在center和center1之间 left, right center, center 1 while left 0 and right n and s[left] s[right]: left - 1 right 1 length right - left - 1 if length max_len: max_len length begin left 1 return s[begin:begin max_len]4.2 为什么中心扩展实际表现优于动态规划只看大O的话动态规划和中心扩展都是O(n²)但实际跑起来中心扩展明显更快。原因有两个一是常数因子小。动态规划有两层循环每层循环内部都要做数组访问、赋值和判断中心扩展只有一层循环枚举中心内部的while虽然也可能扩展很多次但平均下来对于随机字符串扩展几次就停了。二是缓存友好。动态规划要频繁随机访问二维数组的各个位置CPU缓存的命中率不高中心扩展访问的是连续的字符串切片内存访问模式更线性。我实测过LeetCode上的长测试用例比如一个超长的“aaaaaaaaaa……”这样的字符串中心扩展的每个中心都会扩展到边界最坏情况依然是O(n²)但跑起来还是远快于动态规划。原因就在于它的内存访问模式更好。4.3 中心扩展的一个优化技巧对于全相同的字符串比如n5000的全‘a’串中心扩展的时间确实会退化。每个中心的扩展长度都接近n总操作次数是O(n²)。不过实践中这种用例不多而且即使在最坏情况下中心扩展也依然能跑完只是时间稍长。如果真想加速可以在中心扩展之前做一步处理把所有连续相同的字符压缩成一个候选中心。因为“aaaa”这样的串无论从哪个‘a’开始扩展结果都一样。但这样做会改变字符串的索引对应关系实现起来复杂度上升不少性价比不高。我自己的经验是面试时能写出标准中心扩展就够了这个优化可以作为加分项提一嘴但不要在现场写。5. Manacher算法O(n)的真正最优解5.1 为什么需要Manacher中心扩展虽然常数小但最坏情况还是O(n²)。在字符串长度达到10⁵甚至10⁶的场景下O(n²)是绝对不可接受的。这个时候就要请出Manacher算法了。Manacher算法由Manacher在1975年提出核心思想是利用已经计算过的回文信息避免重复扩展。它能在O(n)时间内找出最长回文子串是理论上限——因为任何算法至少要读一遍字符串。Manacher的第一反应都是“这东西好难”。我一开始也这么觉得直到我把它的逻辑拆成三步才发现它其实没有那么神秘预处理、利用对称性、维护右边界。5.2 第一步预处理统一奇偶前面说过回文中心有两种单字符和双字符空隙。Manacher用了一个巧妙的方法统一处理在字符串的所有字符之间包括首尾插入一个特殊字符比如‘#’。原始串abcba 预处理后#a#b#c#b#a#插入之后原串中所有回文子串在预处理串中都变成了奇数长度中心都变成了某个具体字符可能是原字符也可能是‘#’。这样一来我们只需要处理一种情况。这里有个细节插入的字符必须不在原字符串中出现。我在一次交流中看到有人用空格插入结果原字符串里正好有空格导致算法出错。选‘#’、‘$’这类不常见的字符都可以但注意别选ASCII码跟原字符冲突的。5.3 第二步维护臂展数组和右边界预处理后的字符串记为t我们需要计算一个数组p其中p[i]表示以t[i]为中心的最大回文半径臂展这个概念可能有点抽象我实际举例说明。比如t #a#b#a#以中间的‘b’为中心p[3] 3表示半径覆盖3个字符即#a#这一小段。真正回文串的原始长度可以用p[i] - 1反推回来。算法的核心是维护两个变量center当前能覆盖到最右边界的回文串的中心位置right这个回文串的右边界开区间当我们在遍历i时如果i right说明i在当前已知最大回文的覆盖范围内。根据回文的对称性i关于center的对称点j 2 * center - i我们之前已经计算过p[j]。那么p[i]至少可以取min(p[j], right - i)。这句话就是Manacher的全部精髓。它利用了“回文内部的对称性”——既然center左右的字符是完全对称的那以i为中心的回文至少跟以j为中心的回文一样长除非j的回文超出了right的边界这时候就只能保守地取right - i再继续扩展。看代码更直观def longestPalindrome(s: str) - str: # 预处理 t [#] for ch in s: t.append(ch) t.append(#) t .join(t) n len(t) p [0] * n center, right 0, 0 for i in range(n): # 利用对称性初始化p[i] if i right: mirror 2 * center - i p[i] min(p[mirror], right - i) else: p[i] 1 # 中心扩展尝试扩大回文 while i - p[i] 0 and i p[i] n and t[i - p[i]] t[i p[i]]: p[i] 1 # 更新center和right if i p[i] right: center i right i p[i] # 找出最优结果 max_len 0 center_idx 0 for i in range(n): if p[i] - 1 max_len: max_len p[i] - 1 center_idx i # 映射回原串 begin (center_idx - max_len) // 2 return s[begin:begin max_len]5.4 为什么Manacher是O(n)你可能已经注意到while循环里每一步都会把right往右推。而right最多从0增加到n所以整个算法中所有while循环的总执行次数是O(n)。再加上外层循环也是O(n)总复杂度就是O(n)。这个推理非常关键。Manacher并不是“每次扩展都成功”而是“扩展成功的次数加起来不超过n”。它巧妙地利用了一个事实right只会向右移动不会回退。这是它线性复杂度的根本保证。5.5 Manacher的实际应用场景有些人觉得Manacher太冷门面试很少考。这句话只对了一半。确实大多数面试官不会要求你手写Manacher能写出中心扩展就已经很好了。但Manacher的思路在很多字符串题目中都有变体求字符串的“最长双回文子串”两个相邻回文串的最大总长求前缀或后缀中的最长回文在字符范围受限的场合求解回文相关问题更重要的是Manacher体现的“利用对称性避免重复计算”的思想在KMP、Z算法、AC自动机等字符串算法中都能看到影子。理解它对整体提升字符串算法能力很有帮助。6. 横向对比与工程选型建议6.1 四种解法全对比我用一张表把这四种方案梳理清楚方法时间复杂度空间复杂度实现难度适用场景暴力枚举O(n³)O(1)极低仅用于正确性验证动态规划O(n²)O(n²)中等n ≤ 5000的笔试中心扩展O(n²)O(1)低n ≤ 5000面试首选ManacherO(n)O(n)高n ≥ 10⁵竞赛或工程实际开发中字符串长度通常不会太大中心扩展完全够用。但如果你在处理基因序列、长文本分析这类超长字符串Manacher就是必须掌握的了。6.2 面试时怎么写才能拿高分我的建议是面试时优先写中心扩展然后用口述把Manacher的思路讲清楚。这是性价比最高的策略。原因很实在中心扩展代码短、逻辑清晰、两分钟就能写完面试官马上能看懂不容易出错。而Manacher虽然更优但边界条件极多现场手写出bug的概率很大。一旦写错面试官对你的印象反而会打折扣。我在面试别人的时候见过不少候选人信誓旦旦说“我会Manacher”结果写到一半卡住最后代码没调通。这种情况很尴尬。反倒是老老实实写中心扩展、然后清晰说明Manacher原理的候选人我会给更高的评价。6.3 工程上怎么选如果是在项目里真需要处理回文相关逻辑我看过一些开源的实现比如某些字符串匹配库选的是Manacher算法的变体。原因很简单高性能要求的场景O(n)和O(n²)在数据量上来之后差距非常悬殊。但如果只是偶尔用一次不要为了炫技引入一个难维护的算法。维护成本也是成本。代码里写一个注释清晰的中心扩展比写一个没人能改的Manacher要实用得多。7. 代码实现的细节与验证7.1 环境准备与测试数据这道题在几乎所有主流语言里都能写我平时用Python和C刷。Python写起来最快C跑起来性能最好。这里给出C的Manacher实现方便对比class Solution { public: string longestPalindrome(string s) { // 预处理 string t #; for (char c : s) { t c; t #; } int n t.size(); vectorint p(n, 0); int center 0, right 0; for (int i 0; i n; i) { if (i right) { int mirror 2 * center - i; p[i] min(p[mirror], right - i); } else { p[i] 1; } while (i - p[i] 0 i p[i] n t[i - p[i]] t[i p[i]]) { p[i]; } if (i p[i] right) { center i; right i p[i]; } } int max_len 0, center_idx 0; for (int i 0; i n; i) { if (p[i] - 1 max_len) { max_len p[i] - 1; center_idx i; } } int begin (center_idx - max_len) / 2; return s.substr(begin, max_len); } };7.2 测试用例设计心得刷题时很多人只跑示例就交了这是大忌。这道题的边界条件非常多我整理了一套固定的测试集每次写完必跑空字符串输入“”输出“”单字符字符串输入“a”输出“a”全相同字符输入“aaaa”输出“aaaa”两个字符输入“ab”输出“a”输入“aa”输出“aa”回文在开头输入“abacdfg”输出“aba”回文在结尾输入“xyzcbaabc”输出“baa”偶数长度回文输入“cbbd”输出“bb”这些用例基本覆盖了所有分支。特别是“ab”这种两个字符的用例很能暴露那些没考虑偶数回文的小bug。7.3 如何快速定位问题如果代码跑错了先别急着看算法逻辑用最简单的排查法加打印输出每个中心附近的p值或者dp表的值。比如写中心扩展时我会在每次更新max_len的地方打印当前回文串看它是不是真的是回文。这样能很快定位到“扩展边界是否越界”或者“索引映射是否正确”这些问题。Manacher则更依赖对“right - i”这个边界条件的理解。如果发现某次计算结果偏大大概率是初始化p[i]时取了不该取的min值或者while循环的边界写错了。8. 常见问题排查与避坑指南8.1 动态规划的三个常见错误动态规划的写法新手很容易栽在下面这几个地方第一个错误是遍历顺序不对。有些同学写出双层循环i从0到nj从i到n然后直接套状态转移方程。这样算dp[i][j]时dp[i1][j-1]还没算结果全错。原因在于状态转移依赖的是“长度更短”的子串必须先算短的再算长的。第二个错误是dp表的初始化。如果只用默认的False长度为2且首尾相等的回文判定就会出错。我的建议是先初始化对角线为True再在循环里单独处理length 2的情况这样逻辑最清晰。第三个错误是记录答案的时机。有些人只更新dp表忘了同步更新最长长度和起始位置。最后算完再扫描一遍dp表当然也能得到答案但平白多了一轮O(n²)的扫描不值。8.2 中心扩展的两个常见错误中心扩展相对简单但有两个经典坑第一个坑是偶数回文没有处理。只枚举单字符中心导致“abba”这类偶数长度回文永远找不到。这属于思路不完整写之前就应该想到。第二个坑是while循环里的边界条件。我见过有人写成while left right而不是while left 0 and right n结果要么数组越界要么死循环。记住left是向左扩展的指针right是向右扩展的指针它们的上下界必须同时检查。8.3 Manacher的三个进阶防错点Manacher的坑更多我列三个最隐蔽的第一个是关于p[i]的初始化。p[i] min(p[mirror], right - i)是核心但很多人不理解为什么是right - i而不是right - i 1。这取决于right的定义如果right是开区间不包含回文串最后一个字符的位置那么i到right的距离就是right - i个字符。用闭区间定义的话就变成right - i 1。两种定义都行但必须前后一致。我自己习惯用开区间定义代码里也这么写。第二个是关于下标映射。预处理串中回文中心是center_idx回文半径是p[center_idx]原始串中回文的起始位置是(center_idx - max_len) // 2。很多人在这个映射上出错多试试几个用例就能发现规律。第三个是中心扩展后更新right的时机。必须在while循环结束后更新因为while循环可能把p[i]扩大这时候i p[i]才是真正的右边界。8.4 复盘总结我踩过的那些坑我自己第一次完整跑通Manacher花了不少时间。最大的教训是不要死记代码要把right、center、p[i]这些变量在纸面上一层层推演一遍推完再写代码就顺了。给大家一个推演建议拿一个短字符串比如“abba”手工模拟Manacher的每一步。把t数组写在纸上依次计算每个i对应的p[i]标记center和right的变化。整个过程大概10分钟做完之后你就发现这个算法真的没有想象中那么难。另一个经验是学习和实际应用结合写完之后找几个不同的题源做同类题巩固一下。比如求前缀回文、求至少添加多少字符能使整个字符串变成回文串这类变体都建立在Manacher之上。做两三道变体题你对Manacher的理解会上一个台阶。 
长河君 · 2026/10/13 3:33:49 · 阅读 1.2k 最长回文子串全解析：从动态规划到Manacher的进阶之路
1. 从一道高频面试题说起最长回文子串几乎每个刷过LeetCode的人都见过它第5题难度中等。但你要是真去统计一下这道题在面试里出现的频率绝对能排进字符串类题目的前三。我见过不少候选人能把动态规划的代码背得滚瓜烂熟但被问到“为什么要从长度短的子串开始遍历”就卡住了也有人写出了中心扩展却说不清为什么时间复杂度是O(n²)。这恰恰说明很多人只是记住了代码并没有真正理解这个问题的本质。这篇东西不是单纯给你讲题解我想把这道题彻底拆开从暴力解法一步步推导到最优解把每种思路的动机、细节、坑都讲透。无论你是准备面试、刷竞赛还是想系统理解字符串处理这篇文章都值得看完。我把话放在前面最长回文子串不是一道需要死记硬背的题它是一把理解动态规划、双指针和字符串优化的钥匙。先说一个很多人问过我的问题最长回文子串和最长回文子序列有什么区别子串要求连续子序列不要求连续。比如字符串“abca”它的最长回文子串是“a”或“b”或“c”长度1但最长回文子序列是“aba”或“aca”长度3。很多初学者在这里就绕晕了所以先把这个边界划清楚后面的讨论才不跑偏。2. 暴力法最容易想到也最容易超时2.1 暴力法到底在枚举什么暴力法的思路非常直白枚举所有可能的子串检查每一个子串是不是回文记录其中最长的那个。假设字符串长度为n子串总数是O(n²)检查一个子串是否是回文需要O(n)的时间所以总复杂度是O(n³)。用代码写出来就是def longestPalindrome(s: str) - str: n len(s) if n 2: return s max_len 1 begin 0 for i in range(n - 1): for j in range(i 1, n): if j - i 1 max_len and isPalindrome(s, i, j): max_len j - i 1 begin i return s[begin:begin max_len] def isPalindrome(s: str, left: int, right: int) - bool: while left right: if s[left] ! s[right]: return False left 1 right - 1 return True这段代码逻辑本身没错但在LeetCode上跑基本就是超时的命。n稍微大一点比如1000三层循环就是10亿次操作放在任何语言里都扛不住。2.2 为什么暴力法依然值得分析我不建议你直接跳过暴力法。原因有两个第一暴力法是所有优化方案的“基准线”。动态规划、中心扩展、Manacher算法本质上都是在做同一件事减少“枚举子串”和“判断回文”这两部分的开销。你只有清楚暴力法慢在哪里才能理解后续每一点优化到底优化了什么。第二暴力法提供了一个最简单的验证方法。我在实际调试优化算法时经常写一个暴力版的结果作为“标准答案”拿优化算法的输出跟它对比。特别是Manacher这种容易出边界bug的算法没有暴力法做参照错了都不知道错在哪。3. 动态规划用空间换时间的经典思路3.1 状态定义与状态转移动态规划的核心是把“判断一个子串是不是回文”这件事拆成更小的子问题。定义一个二维布尔数组dp[i][j]表示子串s[i:j1]i和j是闭区间是否是回文。那么状态转移方程是dp[i][j] (s[i] s[j]) and dp[i1][j-1]这个方程的理解很关键一个子串是回文必须同时满足两个条件——首尾字符相等并且去掉首尾之后剩下的部分也是回文。举个例子判断“ababa”是否为回文首尾都是‘a’相等再看“bab”首尾都是‘b’相等再看“a”单个字符是回文。一层层往里剥这就是动态规划的思维。3.2 为什么必须按长度遍历这几乎是这道题面试时必问的一个点。先看错误示范按i从小到大、j从大到小或从小到大遍历。比如先算dp[0][4]需要用到dp[1][3]但此时dp[1][3]还没算出来拿到的就是初始值false结果自然错了。正确做法是按子串长度从小到大遍历先算所有长度为1的子串再算所有长度为2的然后是长度为3的……这样当计算dp[i][j]时dp[i1][j-1]对应的子串长度为j-i-1一定比当前子串长度小必然已经计算过。def longestPalindrome(s: str) - str: n len(s) if n 2: return s dp [[False] * n for _ in range(n)] max_len 1 begin 0 # 长度为1的子串都是回文 for i in range(n): dp[i][i] True # 按长度递增遍历 for length in range(2, n 1): for i in range(n - length 1): j i length - 1 if s[i] ! s[j]: dp[i][j] False else: if length 2: dp[i][j] True else: dp[i][j] dp[i 1][j - 1] if dp[i][j] and length max_len: max_len length begin i return s[begin:begin max_len]3.3 动态规划的两个隐藏重点说两个容易忽略的细节。第一个是长度为2的边界处理。当s[i]s[j]且length2时dp[i1][j-1]实际上是dp[i1][i]这在我们的表中没有被初始化直接访问会得到false。所以必须单独处理长度为2且首尾相等就是回文。第二个是空间复杂度的代价。dp表是n×n的布尔矩阵空间复杂度O(n²)。当n5000时就是2500万个布尔值虽然Python的False/True是单例但二维列表本身的开销也不小。这也是为什么实际工程中动态规划不是首选——它虽然把时间复杂度降到了O(n²)但空间开销太大。有人会问能不能把dp表压缩成一维答案是不能简单地滚动数组因为dp[i][j]依赖的是dp[i1][j-1]在二维表里是“左下角”的值。如果你按长度遍历每一层的计算会跨行访问滚动数组没法保证被依赖的值不被覆盖。这也是动态规划解法的一个天然局限。4. 中心扩展常数级优化的胜利4.1 中心扩展的基本思路动态规划的O(n²)时间和O(n²)空间其实还有优化空间。换个角度想回文串的本质是什么是“围绕中心对称”。那与其枚举子串再判断不如直接枚举“中心”然后向两边扩展直到不能扩展为止。这个思路看起来很简单但它避开了动态规划最耗内存的dp表空间复杂度直接降到O(1)时间复杂度依然是O(n²)——因为枚举中心是O(n)的每个中心最多扩展O(n)次。这里有个容易踩坑的地方回文中心有两种。奇数长度的回文中心是单个字符偶数长度的回文中心是两个字符之间的空隙。比如“aba”的中心是‘b’“abba”的中心是“bb”中间。所以枚举中心时要分别处理这两种情况。def longestPalindrome(s: str) - str: n len(s) if n 2: return s max_len 1 begin 0 for center in range(n): # 奇数长度中心是center left, right center, center while left 0 and right n and s[left] s[right]: left - 1 right 1 # 扩展结束后回文范围是[left1, right-1] length right - left - 1 if length max_len: max_len length begin left 1 # 偶数长度中心在center和center1之间 left, right center, center 1 while left 0 and right n and s[left] s[right]: left - 1 right 1 length right - left - 1 if length max_len: max_len length begin left 1 return s[begin:begin max_len]4.2 为什么中心扩展实际表现优于动态规划只看大O的话动态规划和中心扩展都是O(n²)但实际跑起来中心扩展明显更快。原因有两个一是常数因子小。动态规划有两层循环每层循环内部都要做数组访问、赋值和判断中心扩展只有一层循环枚举中心内部的while虽然也可能扩展很多次但平均下来对于随机字符串扩展几次就停了。二是缓存友好。动态规划要频繁随机访问二维数组的各个位置CPU缓存的命中率不高中心扩展访问的是连续的字符串切片内存访问模式更线性。我实测过LeetCode上的长测试用例比如一个超长的“aaaaaaaaaa……”这样的字符串中心扩展的每个中心都会扩展到边界最坏情况依然是O(n²)但跑起来还是远快于动态规划。原因就在于它的内存访问模式更好。4.3 中心扩展的一个优化技巧对于全相同的字符串比如n5000的全‘a’串中心扩展的时间确实会退化。每个中心的扩展长度都接近n总操作次数是O(n²)。不过实践中这种用例不多而且即使在最坏情况下中心扩展也依然能跑完只是时间稍长。如果真想加速可以在中心扩展之前做一步处理把所有连续相同的字符压缩成一个候选中心。因为“aaaa”这样的串无论从哪个‘a’开始扩展结果都一样。但这样做会改变字符串的索引对应关系实现起来复杂度上升不少性价比不高。我自己的经验是面试时能写出标准中心扩展就够了这个优化可以作为加分项提一嘴但不要在现场写。5. Manacher算法O(n)的真正最优解5.1 为什么需要Manacher中心扩展虽然常数小但最坏情况还是O(n²)。在字符串长度达到10⁵甚至10⁶的场景下O(n²)是绝对不可接受的。这个时候就要请出Manacher算法了。Manacher算法由Manacher在1975年提出核心思想是利用已经计算过的回文信息避免重复扩展。它能在O(n)时间内找出最长回文子串是理论上限——因为任何算法至少要读一遍字符串。Manacher的第一反应都是“这东西好难”。我一开始也这么觉得直到我把它的逻辑拆成三步才发现它其实没有那么神秘预处理、利用对称性、维护右边界。5.2 第一步预处理统一奇偶前面说过回文中心有两种单字符和双字符空隙。Manacher用了一个巧妙的方法统一处理在字符串的所有字符之间包括首尾插入一个特殊字符比如‘#’。原始串abcba 预处理后#a#b#c#b#a#插入之后原串中所有回文子串在预处理串中都变成了奇数长度中心都变成了某个具体字符可能是原字符也可能是‘#’。这样一来我们只需要处理一种情况。这里有个细节插入的字符必须不在原字符串中出现。我在一次交流中看到有人用空格插入结果原字符串里正好有空格导致算法出错。选‘#’、‘$’这类不常见的字符都可以但注意别选ASCII码跟原字符冲突的。5.3 第二步维护臂展数组和右边界预处理后的字符串记为t我们需要计算一个数组p其中p[i]表示以t[i]为中心的最大回文半径臂展这个概念可能有点抽象我实际举例说明。比如t #a#b#a#以中间的‘b’为中心p[3] 3表示半径覆盖3个字符即#a#这一小段。真正回文串的原始长度可以用p[i] - 1反推回来。算法的核心是维护两个变量center当前能覆盖到最右边界的回文串的中心位置right这个回文串的右边界开区间当我们在遍历i时如果i right说明i在当前已知最大回文的覆盖范围内。根据回文的对称性i关于center的对称点j 2 * center - i我们之前已经计算过p[j]。那么p[i]至少可以取min(p[j], right - i)。这句话就是Manacher的全部精髓。它利用了“回文内部的对称性”——既然center左右的字符是完全对称的那以i为中心的回文至少跟以j为中心的回文一样长除非j的回文超出了right的边界这时候就只能保守地取right - i再继续扩展。看代码更直观def longestPalindrome(s: str) - str: # 预处理 t [#] for ch in s: t.append(ch) t.append(#) t .join(t) n len(t) p [0] * n center, right 0, 0 for i in range(n): # 利用对称性初始化p[i] if i right: mirror 2 * center - i p[i] min(p[mirror], right - i) else: p[i] 1 # 中心扩展尝试扩大回文 while i - p[i] 0 and i p[i] n and t[i - p[i]] t[i p[i]]: p[i] 1 # 更新center和right if i p[i] right: center i right i p[i] # 找出最优结果 max_len 0 center_idx 0 for i in range(n): if p[i] - 1 max_len: max_len p[i] - 1 center_idx i # 映射回原串 begin (center_idx - max_len) // 2 return s[begin:begin max_len]5.4 为什么Manacher是O(n)你可能已经注意到while循环里每一步都会把right往右推。而right最多从0增加到n所以整个算法中所有while循环的总执行次数是O(n)。再加上外层循环也是O(n)总复杂度就是O(n)。这个推理非常关键。Manacher并不是“每次扩展都成功”而是“扩展成功的次数加起来不超过n”。它巧妙地利用了一个事实right只会向右移动不会回退。这是它线性复杂度的根本保证。5.5 Manacher的实际应用场景有些人觉得Manacher太冷门面试很少考。这句话只对了一半。确实大多数面试官不会要求你手写Manacher能写出中心扩展就已经很好了。但Manacher的思路在很多字符串题目中都有变体求字符串的“最长双回文子串”两个相邻回文串的最大总长求前缀或后缀中的最长回文在字符范围受限的场合求解回文相关问题更重要的是Manacher体现的“利用对称性避免重复计算”的思想在KMP、Z算法、AC自动机等字符串算法中都能看到影子。理解它对整体提升字符串算法能力很有帮助。6. 横向对比与工程选型建议6.1 四种解法全对比我用一张表把这四种方案梳理清楚方法时间复杂度空间复杂度实现难度适用场景暴力枚举O(n³)O(1)极低仅用于正确性验证动态规划O(n²)O(n²)中等n ≤ 5000的笔试中心扩展O(n²)O(1)低n ≤ 5000面试首选ManacherO(n)O(n)高n ≥ 10⁵竞赛或工程实际开发中字符串长度通常不会太大中心扩展完全够用。但如果你在处理基因序列、长文本分析这类超长字符串Manacher就是必须掌握的了。6.2 面试时怎么写才能拿高分我的建议是面试时优先写中心扩展然后用口述把Manacher的思路讲清楚。这是性价比最高的策略。原因很实在中心扩展代码短、逻辑清晰、两分钟就能写完面试官马上能看懂不容易出错。而Manacher虽然更优但边界条件极多现场手写出bug的概率很大。一旦写错面试官对你的印象反而会打折扣。我在面试别人的时候见过不少候选人信誓旦旦说“我会Manacher”结果写到一半卡住最后代码没调通。这种情况很尴尬。反倒是老老实实写中心扩展、然后清晰说明Manacher原理的候选人我会给更高的评价。6.3 工程上怎么选如果是在项目里真需要处理回文相关逻辑我看过一些开源的实现比如某些字符串匹配库选的是Manacher算法的变体。原因很简单高性能要求的场景O(n)和O(n²)在数据量上来之后差距非常悬殊。但如果只是偶尔用一次不要为了炫技引入一个难维护的算法。维护成本也是成本。代码里写一个注释清晰的中心扩展比写一个没人能改的Manacher要实用得多。7. 代码实现的细节与验证7.1 环境准备与测试数据这道题在几乎所有主流语言里都能写我平时用Python和C刷。Python写起来最快C跑起来性能最好。这里给出C的Manacher实现方便对比class Solution { public: string longestPalindrome(string s) { // 预处理 string t #; for (char c : s) { t c; t #; } int n t.size(); vectorint p(n, 0); int center 0, right 0; for (int i 0; i n; i) { if (i right) { int mirror 2 * center - i; p[i] min(p[mirror], right - i); } else { p[i] 1; } while (i - p[i] 0 i p[i] n t[i - p[i]] t[i p[i]]) { p[i]; } if (i p[i] right) { center i; right i p[i]; } } int max_len 0, center_idx 0; for (int i 0; i n; i) { if (p[i] - 1 max_len) { max_len p[i] - 1; center_idx i; } } int begin (center_idx - max_len) / 2; return s.substr(begin, max_len); } };7.2 测试用例设计心得刷题时很多人只跑示例就交了这是大忌。这道题的边界条件非常多我整理了一套固定的测试集每次写完必跑空字符串输入“”输出“”单字符字符串输入“a”输出“a”全相同字符输入“aaaa”输出“aaaa”两个字符输入“ab”输出“a”输入“aa”输出“aa”回文在开头输入“abacdfg”输出“aba”回文在结尾输入“xyzcbaabc”输出“baa”偶数长度回文输入“cbbd”输出“bb”这些用例基本覆盖了所有分支。特别是“ab”这种两个字符的用例很能暴露那些没考虑偶数回文的小bug。7.3 如何快速定位问题如果代码跑错了先别急着看算法逻辑用最简单的排查法加打印输出每个中心附近的p值或者dp表的值。比如写中心扩展时我会在每次更新max_len的地方打印当前回文串看它是不是真的是回文。这样能很快定位到“扩展边界是否越界”或者“索引映射是否正确”这些问题。Manacher则更依赖对“right - i”这个边界条件的理解。如果发现某次计算结果偏大大概率是初始化p[i]时取了不该取的min值或者while循环的边界写错了。8. 常见问题排查与避坑指南8.1 动态规划的三个常见错误动态规划的写法新手很容易栽在下面这几个地方第一个错误是遍历顺序不对。有些同学写出双层循环i从0到nj从i到n然后直接套状态转移方程。这样算dp[i][j]时dp[i1][j-1]还没算结果全错。原因在于状态转移依赖的是“长度更短”的子串必须先算短的再算长的。第二个错误是dp表的初始化。如果只用默认的False长度为2且首尾相等的回文判定就会出错。我的建议是先初始化对角线为True再在循环里单独处理length 2的情况这样逻辑最清晰。第三个错误是记录答案的时机。有些人只更新dp表忘了同步更新最长长度和起始位置。最后算完再扫描一遍dp表当然也能得到答案但平白多了一轮O(n²)的扫描不值。8.2 中心扩展的两个常见错误中心扩展相对简单但有两个经典坑第一个坑是偶数回文没有处理。只枚举单字符中心导致“abba”这类偶数长度回文永远找不到。这属于思路不完整写之前就应该想到。第二个坑是while循环里的边界条件。我见过有人写成while left right而不是while left 0 and right n结果要么数组越界要么死循环。记住left是向左扩展的指针right是向右扩展的指针它们的上下界必须同时检查。8.3 Manacher的三个进阶防错点Manacher的坑更多我列三个最隐蔽的第一个是关于p[i]的初始化。p[i] min(p[mirror], right - i)是核心但很多人不理解为什么是right - i而不是right - i 1。这取决于right的定义如果right是开区间不包含回文串最后一个字符的位置那么i到right的距离就是right - i个字符。用闭区间定义的话就变成right - i 1。两种定义都行但必须前后一致。我自己习惯用开区间定义代码里也这么写。第二个是关于下标映射。预处理串中回文中心是center_idx回文半径是p[center_idx]原始串中回文的起始位置是(center_idx - max_len) // 2。很多人在这个映射上出错多试试几个用例就能发现规律。第三个是中心扩展后更新right的时机。必须在while循环结束后更新因为while循环可能把p[i]扩大这时候i p[i]才是真正的右边界。8.4 复盘总结我踩过的那些坑我自己第一次完整跑通Manacher花了不少时间。最大的教训是不要死记代码要把right、center、p[i]这些变量在纸面上一层层推演一遍推完再写代码就顺了。给大家一个推演建议拿一个短字符串比如“abba”手工模拟Manacher的每一步。把t数组写在纸上依次计算每个i对应的p[i]标记center和right的变化。整个过程大概10分钟做完之后你就发现这个算法真的没有想象中那么难。另一个经验是学习和实际应用结合写完之后找几个不同的题源做同类题巩固一下。比如求前缀回文、求至少添加多少字符能使整个字符串变成回文串这类变体都建立在Manacher之上。做两三道变体题你对Manacher的理解会上一个台阶。