1. 这个“简单题”为什么难倒了一批人——HJ85的题目拆解与常见误区先说结论HJ85 最长回文子串是华为机试里出镜率极高的一道题但它不只是一道“背模板”的题。很多人把暴力枚举写上去样例过了提交就超时还有人记住了经典解法却在边界条件上翻车。我自己在刷题群和帮人改代码时见过太多次这种场面一个回文串判断写错、一个左右指针偏移搞反、一个空串没处理半小时就没了。题目本身不复杂给定一个字符串找出其中最长的回文子串输出它的长度。这里有两个概念必须先抠清楚。第一什么是回文正着读和反着读都一样比如abba、racecar。第二什么是子串原字符串中连续的一段这和“子序列”有本质区别。子序列允许跳过字符子串不允许。比如abcba中abc是子串而aca虽然也是回文但不是子串因为它在原串中隔着b这种只能叫回文子序列不在本题讨论范围内。很多人一上来就写三层循环枚举所有子串的起点和终点再判断这个子串是不是回文。三层循环套进去复杂度 O(n^3)在字符串长度 1000 的时候就跑到很吃力了。更常见的错误是把原串反转然后求两个串的最长公共子串觉得“反转后还一样的连续子串就是回文”。这个思路看起来漂亮实际上有漏洞。我构造一个反例s abcdecba反转后得到abcedcba这两个串的最长公共子串是abc长度为 3但abc显然不是回文。而真正的答案其实是bcdcb长度 5。为什么反转法会失灵因为反转串中出现的公共子串无法保证它对应回文串的对称位置只有额外校验两个串中的位置索引才能用而这种校验写起来比老老实实做还麻烦。在做任何高效解法之前要抓住回文最本质的性质所有回文串都只有一个“中心”然后向两边对称生长。奇数长度的回文中心是一个字符偶数长度的回文中心是两个字符之间的空隙。这两句话是所有正解的地基。2. 中心扩展法机试里最该优先掌握的解法2.1 为什么是 2n-1 个中心暴力法的浪费在于它枚举的是“子串的两端”然后从两端往中间收缩验证。但回文天然是从内向外长的不是从外向内挤的。一个长度为 n 的字符串可能存在回文中心的位置有多少个每个字符本身是一个奇数中心任意两个相邻字符之间的位置是一个偶数中心。所以总共有 n (n-1) 2n-1 个中心。这里我补一个容易忽略的细节a这种单字符本身就是回文长度为 1它对应奇数中心aa这种双字符回文对应的是两个字符中间的空隙。如果你只遍历字符中心会漏掉所有偶数长度的回文串。2.2 代码实现与逐步推演中心扩展法的代码是所有解法里最短的核心就是一个扩展函数def expand_around_center(s, left, right): n len(s) while left 0 and right n and s[left] s[right]: left - 1 right 1 return right - left - 1 def longest_palindrome(s): if not s: return 0 max_len 0 n len(s) for i in range(n): len_odd expand_around_center(s, i, i) # 奇数中心 len_even expand_around_center(s, i, i 1) # 偶数中心 max_len max(max_len, len_odd, len_even) return max_len拿s abac走一遍流程。i1也就是字符b奇数中心扩展左边s[0]a右边s[2]a相同继续扩再比较s[-1]和s[3]左边越界停止此时回文长度为 3得到aba。如果这时只看奇数中心最大的长度是 3没有问题。但换成abbai1 的奇数中心只能得到长度 1真正的最长回文来自 i1 和 i2 之间的偶数中心扩展后得到长度 4。所以两行调用缺一不可。2.3 边界条件和复杂度复杂度方面每个中心最多向外扩展 n 次一共 2n-1 个中心最坏情况是串里全是同一个字符比如aaaaa每次扩展都会走到边界总时间是 O(n^2)空间 O(1)。这放在 HJ85 的限制下通常 n 1000 量级是完全没有压力的。实测下来1000 长度的随机字符串这个解法在毫秒级就能跑完。边界条件有两点要特别留意。第一while循环里必须先判断left 0和right n再判断s[left] s[right]顺序反了会在 Python 里直接抛索引越界异常。第二返回的是right - left - 1因为退出循环时 left 和 right 都已经多走了一步实际回文区间是(left, right)开区间长度要减 1。这两个点看着小但手撕代码时非常容易写错。2.4 如果题目要求输出子串本身有些机试版本会要求返回最长回文子串而不是长度改法也很简单在更新 max_len 的同时记住当前中心对应的起始位置。以奇数中心为例回文起点是i - (max_len - 1) // 2终点是i max_len // 2。记住这个公式面试时就不用手忙脚乱现推了。3. 动态规划解法状态表里藏着回文递推逻辑3.1 状态定义与转移方程动态规划解决这个问题的思路完全不同它不再从中心出发而是用一张二维表格记录所有子串是否为回文。定义dp[i][j]表示字符串s[i:j1]是否为回文。状态转移方程是如果s[i] ! s[j]那么dp[i][j] False如果s[i] s[j]当子串长度小于等于 2 时直接是回文当子串长度大于 2 时dp[i][j] dp[i1][j-1]写成代码就是dp[i][j] (s[i] s[j]) and (j - i 2 or dp[i1][j-1])。这里的j - i 2涵盖了长度为 1、2、3 三种情况。为什么长度为 3 也不需要查内部因为aba这种长度为 3 的子串只要两端相等中间那个字符必然是单个字符自然就是回文。3.2 遍历顺序为什么必须按长度从短到长这是动态规划最容易出问题的地方。dp[i][j]依赖dp[i1][j-1]也就是表格中“左下角”的位置。如果按起点 i 从前往后、终点 j 从前往后遍历算dp[i][j]时dp[i1][j-1]可能还没被填出来。正确的做法是按子串长度 L 从 2 到 n 枚举再枚举起点 i终点 j i L - 1 自然确定。这样每次计算依赖的都是长度更短的子串一定已经被填好了。def longest_palindrome_dp(s): n len(s) if n 2: return n dp [[False] * n for _ in range(n)] for i in range(n): dp[i][i] True max_len 1 for L in range(2, n 1): for i in range(n - L 1): j i L - 1 if s[i] s[j] and (L 2 or dp[i1][j-1]): dp[i][j] True max_len max(max_len, L) return max_len3.3 什么时候该选动态规划动态规划解回文的时间复杂度也是 O(n^2)但空间是 O(n^2)。在 HJ85 这种只求最长长度的场景里动态规划并不比中心扩展法有优势反而占了更多内存。我个人的建议是如果题目只是求最长回文子串长度优先中心扩展法如果题目问的是“一共有多少个回文子串”或者“最少分割几次”动态规划的优势才体现出来因为 dp 表可以反复使用。比如回文子串计数问题中心扩展也能做但 dp 的套路更容易扩展成其他回文类问题的通用工具。这道题还有一个可以讨论的点能不能把 dp 表格压缩成一行严格来说可以优化空间但回文 dp 的状态依赖斜对角线滚动数组时需要用临时变量保存上一轮的左下角值写起来绕而且对于 HJ85 的输入规模二维布尔数组在 1000 长度下也就 100 万个元素Python 里大概占用 1MB 级别的内存OJ 完全不会卡。为了追求“优雅”牺牲可读性我觉得不划算。4. 马拉车算法用对称性把复杂度压到 O(n)4.1 为什么需要这个看起来绕的算法中心扩展法的短板在于每个中心独立扩展前面算过的扩展结果无法给后面的中心提供信息。比如aaaaaaaaaa这种全是相同字符的串中心扩展会对每个位置重复向外扩展很多次存在大量重复计算。马拉车Manacher算法就是针对这一点做的优化它在扩展时利用已经算好的回文半径通过对称中心直接给当前中心一个“初始值”避免从头开始比较。这个算法的理解门槛主要在代码层面但它背后的思想并不复杂维护一个已知的最靠右的回文边界如果当前中心在这个边界内部那么它的镜像位置一定在边界的另一侧而镜像位置的回文半径是已知的可以直接借过来作为初始值。4.2 插值预处理把奇偶问题统一掉先用#把字符串填充一遍。aba变成#a#b#a#aa变成#a#a#。这样处理后原串中所有回文都变成了奇数长度因为填充后的字符串首尾和间隔都是#而且原串的回文一定对应新串中以某个字符为中心的回文。这个转换的意义是代码里不再需要分别处理奇数和偶数中心只需要处理一种情况。p[i]表示新串中以位置 i 为中心的最大回文半径注意半径包含中心本身。有个现成的结论p[i] - 1就是原串中以该中心对应的最长回文长度。原因很简单新串中回文串长2*p[i]-1其中#的数量比原串字符多 1 个所以原串长度就是(2*p[i]-1-1)/2 p[i]-1。这个推导建议自己拿#a#b#a#和#a#a#验证一遍比死记结论牢靠。4.3 三个关键变量与代码马拉车的核心维护三个变量center当前能覆盖到最右边界的那段回文的中心right这段回文能覆盖到的最右位置mirror当前遍历位置 i 关于 center 的对称位置mirror 2 * center - i当i right时p[i]至少等于min(p[mirror], right - i)。为什么取最小值因为p[mirror]可能比right - i大一旦超过 right 的范围右边的情况还没探索过不能直接用镜像数据只能先保证在已知范围内对称。def longest_palindrome_manacher(s): if not s: return 0 t # #.join(s) # n len(t) p [0] * n center, right 0, 0 max_radius 1 for i in range(n): if i right: mirror 2 * center - i p[i] min(p[mirror], right - i) while (i - p[i] - 1 0 and i p[i] 1 n and t[i - p[i] - 1] t[i p[i] 1]): p[i] 1 if i p[i] right: center i right i p[i] max_radius max(max_radius, p[i]) return max_radius - 1这段代码有几个容易踩的细节。第一p[i]的初始值可以是 0也可以用1写法不同while 里偏移的写法也不同我给的版本是从 0 开始while 里比较i - p[i] - 1和i p[i] 1逻辑清晰。第二center和right的更新条件是i p[i] right注意不是写成也能过但语义上更准确因为等于时更新并不会扩大覆盖范围还可能导致 center 频繁变化。第三循环结束后t串的 p 数组里最大值减 1 就是答案。4.4 为什么总复杂度是 O(n)马拉车最让人怀疑的点是明明里面还有个 while 循环怎么就 O(n) 了关键原因在于right的单调性。每次 while 扩展时i p[i]一定超过当前的 right然后 right 就更新到这个更远的位置。right 在整个算法过程中只会向右移动最多移动 n 次所以所有 while 循环的总执行次数是 O(n) 的而不是每个 i 都扩展 O(n)。这就是均摊分析的核心逻辑。从实测来看马拉车在超长字符串比如 10 万字符上的优势非常明显而中心扩展法在同样输入下会明显卡顿。对于 HJ85 这种题目马拉车其实属于“会了加分、不会也能过”的解法。但我建议还是要把它的模板记下来因为它能无缝衔接到“输出回文本身”“求第 k 大回文子串”这类进阶题。5. 三种解法横向对比与实战选型5.1 一张表看清差异解法时间复杂度空间复杂度代码行数正确性风险点适用场景暴力枚举O(n^3)O(1)少超时仅限字符串长度很小或用来验证其他解法中心扩展O(n^2)O(1)少边界顺序、奇数/偶数中心遗漏机试首选简洁可靠动态规划O(n^2)O(n^2)中遍历顺序、状态初始化回文计数、回文分割等延伸题马拉车O(n)O(n)较多初始化、right/center 更新超长字符串、面试展示深度5.2 机试中的选择策略我个人的建议非常明确机试优先背熟中心扩展法。原因有三点。第一代码量小手撕时出错的概率低第二O(n^2) 的复杂度在 HJ85 的输入规模下完全够用第三它的扩展逻辑直观万一题目有点变体现场改起来也容易。动态规划可以作为备选方案尤其是你已经非常熟悉 dp 模板的情况下写出来也很快。马拉车在机试里不是必需品它的最大价值在于面试时聊复杂度优化你能把对称性原理讲清楚会是明显的加分项。这里我必须说一个很多人忽略的点算法题的“快”不只是运行得快更是“写完并一次通过”的快。中心扩展法代码短边界清楚调试成本低。马拉车虽然理论复杂度低但如果你在机试压力下花了 15 分钟才把 p 数组写对那它的理论优势就毫无意义。所以选型的逻辑是在保证能通过的前提下选择最不容易写错的方案。5.3 从这道题延伸出去的回文家族最长回文子串只是回文问题的一小部分。我把相关的题目列一下方便你按图索骥回文子串计数LeetCode 647求所有回文子串的数量中心扩展和马拉车都能做最短回文串LeetCode 214在字符串前添加字符使其成为回文这题本质是利用回文前缀会用到 KMP 的失配函数分割回文串 IILeetCode 132最少分割次数是 dp 和回文判断的结合最长回文子序列LeetCode 516注意是子序列不是子串解法用的都是区间 dp刷题时如果能把这几道题串起来理解回文这个专题就吃透了比孤立地背十道题有用得多。6. 实战排坑记录那些让我 W 一次的细节6.1 坑一题目要长度你却输出子串有同学在做 HJ85 时想当然地输出了回文子串本身结果格式错误直接判 WA。这种错误最冤因为本地测试样例可能恰好通过了样例里最长回文子串和长度的第一位数字相同或者判题器不区分但提交就暴露。建议严格按题目的输出要求写并且在本地自测时故意构造几个“最长回文子串唯一且开头字符与长度数字不同”的用例。6.2 坑二边界判断顺序反了中心扩展法的核心循环是while left 0 and right n and s[left] s[right]有人会写成while s[left] s[right] and left 0 and right n。表面上只是顺序不同但一旦 left 或 right 越界程序会立刻崩溃。Python 的and是短路运算只要把边界判断放在最前面就能保证后续的索引访问是安全的。这个顺序问题在马拉车的 while 里同样要小心。6.3 坑三把“子串”做成“子序列”我见过不止一次有人用最长公共子序列LCS的模板去解最长回文子串。思路是把原串反转求原串和反转串的最长公共子序列然后拿到一个“看起来是回文”的结果。但正如前文abcdecba的例子所展示的子序列不要求连续求出来的结果可能根本不在原串中连续出现完全没有意义。在做题之前先看清题目说的是 substring 还是 subsequence这决定了完全不同的解法。6.4 坑四马拉车的哨兵设计不合理有些马拉车模板会在字符串两端加上^和$两个特殊哨兵字符目的是让 while 循环不用检查越界。这个做法本身没问题但前提是这两个字符绝不能出现在原字符串中。如果输入可能包含任意 ASCII 字符用^和$就有风险。更稳妥的做法是用#插值然后老老实实写越界判断或者用chr(0)、chr(1)这种不可能出现的控制字符当哨兵。我自己更喜欢不用链路哨兵、只写越界判断的版本虽然代码长几行但逻辑完全在自己掌控中不会因为哨兵冲突出莫名其妙的 bug。6.5 坑五自测用例覆盖面太窄很多人交上去之前只测了abcba和abba觉得稳了结果漏了空串、单字符、全相同字符这些边界情况。我把每次做字符串题的自测清单整理了一下空串预期 0单字符a预期 1双字符合相同aa预期 2双字符不同ab预期 1全相同字符aaaa预期 4回文在末尾abccba的子串场景回文跨越大半段xabac的子串场景把这些用例在本地跑一遍能拦下九成的低级错误。更严格的做法是写一个暴力解作为对拍器随机生成字符串对比结果。这是我在刷题阶段最推荐的验证手段没有之一。6.6 坑六忽视了输入字符串的内容范围HJ85 的输入在规定里可能只包含小写字母但有些平台会放宽成大小写字母和数字此时比较要严格区分大小写A和a不相等。如果题目没提“忽略大小写”就默认严格比较。这是个很坑的细节建议读完题先确认字符范围再决定要不要做大小写归一封处理。6.7 对拍验证的落地姿势找一个不会超时的暴力解法和你的优化解法同时跑同一个随机输入一旦结果不一致就缩小字符串长度和生成范围定位出错的最小用例。比如import random def brute_force(s): n len(s) max_len 0 for i in range(n): for j in range(i, n): sub s[i:j1] if sub sub[::-1]: max_len max(max_len, j - i 1) return max_len def random_string(length): return .join(random.choice(abcd) for _ in range(length)) for _ in range(10000): s random_string(random.randint(1, 20)) if brute_force(s) ! longest_palindrome(s): print(mismatch:, s, brute_force(s), longest_palindrome(s)) break这种对拍在笔试准备阶段价值极大因为很多边界问题靠人脑是很难想全的但机器能在一万次随机测试里帮你找到最小反例。把这三个解法变为本能我自己的经验是回文子串这块真正有用的不是背下所有代码而是理解“回文由中心生长”这个直觉。有了这个直觉中心扩展法你可以闭着眼写动态规划只是在给它套一张状态表马拉车则是给同一件事加了一个对称性的缓存。三者是一脉相承的。最后分享一个刷题小习惯每道题提交通过后不要急着开下一题花两分钟想想“如果把输出从长度改成子串本身代码改哪里”“如果字符串变长十倍现有解法还撑得住吗”。这种追问比多做两题更有复利效应。HJ85 这道题做透了回文家族的题你都会轻松很多。
最长回文子串全解析：中心扩展、动态规划与马拉车算法实战对比
1. 这个“简单题”为什么难倒了一批人——HJ85的题目拆解与常见误区先说结论HJ85 最长回文子串是华为机试里出镜率极高的一道题但它不只是一道“背模板”的题。很多人把暴力枚举写上去样例过了提交就超时还有人记住了经典解法却在边界条件上翻车。我自己在刷题群和帮人改代码时见过太多次这种场面一个回文串判断写错、一个左右指针偏移搞反、一个空串没处理半小时就没了。题目本身不复杂给定一个字符串找出其中最长的回文子串输出它的长度。这里有两个概念必须先抠清楚。第一什么是回文正着读和反着读都一样比如abba、racecar。第二什么是子串原字符串中连续的一段这和“子序列”有本质区别。子序列允许跳过字符子串不允许。比如abcba中abc是子串而aca虽然也是回文但不是子串因为它在原串中隔着b这种只能叫回文子序列不在本题讨论范围内。很多人一上来就写三层循环枚举所有子串的起点和终点再判断这个子串是不是回文。三层循环套进去复杂度 O(n^3)在字符串长度 1000 的时候就跑到很吃力了。更常见的错误是把原串反转然后求两个串的最长公共子串觉得“反转后还一样的连续子串就是回文”。这个思路看起来漂亮实际上有漏洞。我构造一个反例s abcdecba反转后得到abcedcba这两个串的最长公共子串是abc长度为 3但abc显然不是回文。而真正的答案其实是bcdcb长度 5。为什么反转法会失灵因为反转串中出现的公共子串无法保证它对应回文串的对称位置只有额外校验两个串中的位置索引才能用而这种校验写起来比老老实实做还麻烦。在做任何高效解法之前要抓住回文最本质的性质所有回文串都只有一个“中心”然后向两边对称生长。奇数长度的回文中心是一个字符偶数长度的回文中心是两个字符之间的空隙。这两句话是所有正解的地基。2. 中心扩展法机试里最该优先掌握的解法2.1 为什么是 2n-1 个中心暴力法的浪费在于它枚举的是“子串的两端”然后从两端往中间收缩验证。但回文天然是从内向外长的不是从外向内挤的。一个长度为 n 的字符串可能存在回文中心的位置有多少个每个字符本身是一个奇数中心任意两个相邻字符之间的位置是一个偶数中心。所以总共有 n (n-1) 2n-1 个中心。这里我补一个容易忽略的细节a这种单字符本身就是回文长度为 1它对应奇数中心aa这种双字符回文对应的是两个字符中间的空隙。如果你只遍历字符中心会漏掉所有偶数长度的回文串。2.2 代码实现与逐步推演中心扩展法的代码是所有解法里最短的核心就是一个扩展函数def expand_around_center(s, left, right): n len(s) while left 0 and right n and s[left] s[right]: left - 1 right 1 return right - left - 1 def longest_palindrome(s): if not s: return 0 max_len 0 n len(s) for i in range(n): len_odd expand_around_center(s, i, i) # 奇数中心 len_even expand_around_center(s, i, i 1) # 偶数中心 max_len max(max_len, len_odd, len_even) return max_len拿s abac走一遍流程。i1也就是字符b奇数中心扩展左边s[0]a右边s[2]a相同继续扩再比较s[-1]和s[3]左边越界停止此时回文长度为 3得到aba。如果这时只看奇数中心最大的长度是 3没有问题。但换成abbai1 的奇数中心只能得到长度 1真正的最长回文来自 i1 和 i2 之间的偶数中心扩展后得到长度 4。所以两行调用缺一不可。2.3 边界条件和复杂度复杂度方面每个中心最多向外扩展 n 次一共 2n-1 个中心最坏情况是串里全是同一个字符比如aaaaa每次扩展都会走到边界总时间是 O(n^2)空间 O(1)。这放在 HJ85 的限制下通常 n 1000 量级是完全没有压力的。实测下来1000 长度的随机字符串这个解法在毫秒级就能跑完。边界条件有两点要特别留意。第一while循环里必须先判断left 0和right n再判断s[left] s[right]顺序反了会在 Python 里直接抛索引越界异常。第二返回的是right - left - 1因为退出循环时 left 和 right 都已经多走了一步实际回文区间是(left, right)开区间长度要减 1。这两个点看着小但手撕代码时非常容易写错。2.4 如果题目要求输出子串本身有些机试版本会要求返回最长回文子串而不是长度改法也很简单在更新 max_len 的同时记住当前中心对应的起始位置。以奇数中心为例回文起点是i - (max_len - 1) // 2终点是i max_len // 2。记住这个公式面试时就不用手忙脚乱现推了。3. 动态规划解法状态表里藏着回文递推逻辑3.1 状态定义与转移方程动态规划解决这个问题的思路完全不同它不再从中心出发而是用一张二维表格记录所有子串是否为回文。定义dp[i][j]表示字符串s[i:j1]是否为回文。状态转移方程是如果s[i] ! s[j]那么dp[i][j] False如果s[i] s[j]当子串长度小于等于 2 时直接是回文当子串长度大于 2 时dp[i][j] dp[i1][j-1]写成代码就是dp[i][j] (s[i] s[j]) and (j - i 2 or dp[i1][j-1])。这里的j - i 2涵盖了长度为 1、2、3 三种情况。为什么长度为 3 也不需要查内部因为aba这种长度为 3 的子串只要两端相等中间那个字符必然是单个字符自然就是回文。3.2 遍历顺序为什么必须按长度从短到长这是动态规划最容易出问题的地方。dp[i][j]依赖dp[i1][j-1]也就是表格中“左下角”的位置。如果按起点 i 从前往后、终点 j 从前往后遍历算dp[i][j]时dp[i1][j-1]可能还没被填出来。正确的做法是按子串长度 L 从 2 到 n 枚举再枚举起点 i终点 j i L - 1 自然确定。这样每次计算依赖的都是长度更短的子串一定已经被填好了。def longest_palindrome_dp(s): n len(s) if n 2: return n dp [[False] * n for _ in range(n)] for i in range(n): dp[i][i] True max_len 1 for L in range(2, n 1): for i in range(n - L 1): j i L - 1 if s[i] s[j] and (L 2 or dp[i1][j-1]): dp[i][j] True max_len max(max_len, L) return max_len3.3 什么时候该选动态规划动态规划解回文的时间复杂度也是 O(n^2)但空间是 O(n^2)。在 HJ85 这种只求最长长度的场景里动态规划并不比中心扩展法有优势反而占了更多内存。我个人的建议是如果题目只是求最长回文子串长度优先中心扩展法如果题目问的是“一共有多少个回文子串”或者“最少分割几次”动态规划的优势才体现出来因为 dp 表可以反复使用。比如回文子串计数问题中心扩展也能做但 dp 的套路更容易扩展成其他回文类问题的通用工具。这道题还有一个可以讨论的点能不能把 dp 表格压缩成一行严格来说可以优化空间但回文 dp 的状态依赖斜对角线滚动数组时需要用临时变量保存上一轮的左下角值写起来绕而且对于 HJ85 的输入规模二维布尔数组在 1000 长度下也就 100 万个元素Python 里大概占用 1MB 级别的内存OJ 完全不会卡。为了追求“优雅”牺牲可读性我觉得不划算。4. 马拉车算法用对称性把复杂度压到 O(n)4.1 为什么需要这个看起来绕的算法中心扩展法的短板在于每个中心独立扩展前面算过的扩展结果无法给后面的中心提供信息。比如aaaaaaaaaa这种全是相同字符的串中心扩展会对每个位置重复向外扩展很多次存在大量重复计算。马拉车Manacher算法就是针对这一点做的优化它在扩展时利用已经算好的回文半径通过对称中心直接给当前中心一个“初始值”避免从头开始比较。这个算法的理解门槛主要在代码层面但它背后的思想并不复杂维护一个已知的最靠右的回文边界如果当前中心在这个边界内部那么它的镜像位置一定在边界的另一侧而镜像位置的回文半径是已知的可以直接借过来作为初始值。4.2 插值预处理把奇偶问题统一掉先用#把字符串填充一遍。aba变成#a#b#a#aa变成#a#a#。这样处理后原串中所有回文都变成了奇数长度因为填充后的字符串首尾和间隔都是#而且原串的回文一定对应新串中以某个字符为中心的回文。这个转换的意义是代码里不再需要分别处理奇数和偶数中心只需要处理一种情况。p[i]表示新串中以位置 i 为中心的最大回文半径注意半径包含中心本身。有个现成的结论p[i] - 1就是原串中以该中心对应的最长回文长度。原因很简单新串中回文串长2*p[i]-1其中#的数量比原串字符多 1 个所以原串长度就是(2*p[i]-1-1)/2 p[i]-1。这个推导建议自己拿#a#b#a#和#a#a#验证一遍比死记结论牢靠。4.3 三个关键变量与代码马拉车的核心维护三个变量center当前能覆盖到最右边界的那段回文的中心right这段回文能覆盖到的最右位置mirror当前遍历位置 i 关于 center 的对称位置mirror 2 * center - i当i right时p[i]至少等于min(p[mirror], right - i)。为什么取最小值因为p[mirror]可能比right - i大一旦超过 right 的范围右边的情况还没探索过不能直接用镜像数据只能先保证在已知范围内对称。def longest_palindrome_manacher(s): if not s: return 0 t # #.join(s) # n len(t) p [0] * n center, right 0, 0 max_radius 1 for i in range(n): if i right: mirror 2 * center - i p[i] min(p[mirror], right - i) while (i - p[i] - 1 0 and i p[i] 1 n and t[i - p[i] - 1] t[i p[i] 1]): p[i] 1 if i p[i] right: center i right i p[i] max_radius max(max_radius, p[i]) return max_radius - 1这段代码有几个容易踩的细节。第一p[i]的初始值可以是 0也可以用1写法不同while 里偏移的写法也不同我给的版本是从 0 开始while 里比较i - p[i] - 1和i p[i] 1逻辑清晰。第二center和right的更新条件是i p[i] right注意不是写成也能过但语义上更准确因为等于时更新并不会扩大覆盖范围还可能导致 center 频繁变化。第三循环结束后t串的 p 数组里最大值减 1 就是答案。4.4 为什么总复杂度是 O(n)马拉车最让人怀疑的点是明明里面还有个 while 循环怎么就 O(n) 了关键原因在于right的单调性。每次 while 扩展时i p[i]一定超过当前的 right然后 right 就更新到这个更远的位置。right 在整个算法过程中只会向右移动最多移动 n 次所以所有 while 循环的总执行次数是 O(n) 的而不是每个 i 都扩展 O(n)。这就是均摊分析的核心逻辑。从实测来看马拉车在超长字符串比如 10 万字符上的优势非常明显而中心扩展法在同样输入下会明显卡顿。对于 HJ85 这种题目马拉车其实属于“会了加分、不会也能过”的解法。但我建议还是要把它的模板记下来因为它能无缝衔接到“输出回文本身”“求第 k 大回文子串”这类进阶题。5. 三种解法横向对比与实战选型5.1 一张表看清差异解法时间复杂度空间复杂度代码行数正确性风险点适用场景暴力枚举O(n^3)O(1)少超时仅限字符串长度很小或用来验证其他解法中心扩展O(n^2)O(1)少边界顺序、奇数/偶数中心遗漏机试首选简洁可靠动态规划O(n^2)O(n^2)中遍历顺序、状态初始化回文计数、回文分割等延伸题马拉车O(n)O(n)较多初始化、right/center 更新超长字符串、面试展示深度5.2 机试中的选择策略我个人的建议非常明确机试优先背熟中心扩展法。原因有三点。第一代码量小手撕时出错的概率低第二O(n^2) 的复杂度在 HJ85 的输入规模下完全够用第三它的扩展逻辑直观万一题目有点变体现场改起来也容易。动态规划可以作为备选方案尤其是你已经非常熟悉 dp 模板的情况下写出来也很快。马拉车在机试里不是必需品它的最大价值在于面试时聊复杂度优化你能把对称性原理讲清楚会是明显的加分项。这里我必须说一个很多人忽略的点算法题的“快”不只是运行得快更是“写完并一次通过”的快。中心扩展法代码短边界清楚调试成本低。马拉车虽然理论复杂度低但如果你在机试压力下花了 15 分钟才把 p 数组写对那它的理论优势就毫无意义。所以选型的逻辑是在保证能通过的前提下选择最不容易写错的方案。5.3 从这道题延伸出去的回文家族最长回文子串只是回文问题的一小部分。我把相关的题目列一下方便你按图索骥回文子串计数LeetCode 647求所有回文子串的数量中心扩展和马拉车都能做最短回文串LeetCode 214在字符串前添加字符使其成为回文这题本质是利用回文前缀会用到 KMP 的失配函数分割回文串 IILeetCode 132最少分割次数是 dp 和回文判断的结合最长回文子序列LeetCode 516注意是子序列不是子串解法用的都是区间 dp刷题时如果能把这几道题串起来理解回文这个专题就吃透了比孤立地背十道题有用得多。6. 实战排坑记录那些让我 W 一次的细节6.1 坑一题目要长度你却输出子串有同学在做 HJ85 时想当然地输出了回文子串本身结果格式错误直接判 WA。这种错误最冤因为本地测试样例可能恰好通过了样例里最长回文子串和长度的第一位数字相同或者判题器不区分但提交就暴露。建议严格按题目的输出要求写并且在本地自测时故意构造几个“最长回文子串唯一且开头字符与长度数字不同”的用例。6.2 坑二边界判断顺序反了中心扩展法的核心循环是while left 0 and right n and s[left] s[right]有人会写成while s[left] s[right] and left 0 and right n。表面上只是顺序不同但一旦 left 或 right 越界程序会立刻崩溃。Python 的and是短路运算只要把边界判断放在最前面就能保证后续的索引访问是安全的。这个顺序问题在马拉车的 while 里同样要小心。6.3 坑三把“子串”做成“子序列”我见过不止一次有人用最长公共子序列LCS的模板去解最长回文子串。思路是把原串反转求原串和反转串的最长公共子序列然后拿到一个“看起来是回文”的结果。但正如前文abcdecba的例子所展示的子序列不要求连续求出来的结果可能根本不在原串中连续出现完全没有意义。在做题之前先看清题目说的是 substring 还是 subsequence这决定了完全不同的解法。6.4 坑四马拉车的哨兵设计不合理有些马拉车模板会在字符串两端加上^和$两个特殊哨兵字符目的是让 while 循环不用检查越界。这个做法本身没问题但前提是这两个字符绝不能出现在原字符串中。如果输入可能包含任意 ASCII 字符用^和$就有风险。更稳妥的做法是用#插值然后老老实实写越界判断或者用chr(0)、chr(1)这种不可能出现的控制字符当哨兵。我自己更喜欢不用链路哨兵、只写越界判断的版本虽然代码长几行但逻辑完全在自己掌控中不会因为哨兵冲突出莫名其妙的 bug。6.5 坑五自测用例覆盖面太窄很多人交上去之前只测了abcba和abba觉得稳了结果漏了空串、单字符、全相同字符这些边界情况。我把每次做字符串题的自测清单整理了一下空串预期 0单字符a预期 1双字符合相同aa预期 2双字符不同ab预期 1全相同字符aaaa预期 4回文在末尾abccba的子串场景回文跨越大半段xabac的子串场景把这些用例在本地跑一遍能拦下九成的低级错误。更严格的做法是写一个暴力解作为对拍器随机生成字符串对比结果。这是我在刷题阶段最推荐的验证手段没有之一。6.6 坑六忽视了输入字符串的内容范围HJ85 的输入在规定里可能只包含小写字母但有些平台会放宽成大小写字母和数字此时比较要严格区分大小写A和a不相等。如果题目没提“忽略大小写”就默认严格比较。这是个很坑的细节建议读完题先确认字符范围再决定要不要做大小写归一封处理。6.7 对拍验证的落地姿势找一个不会超时的暴力解法和你的优化解法同时跑同一个随机输入一旦结果不一致就缩小字符串长度和生成范围定位出错的最小用例。比如import random def brute_force(s): n len(s) max_len 0 for i in range(n): for j in range(i, n): sub s[i:j1] if sub sub[::-1]: max_len max(max_len, j - i 1) return max_len def random_string(length): return .join(random.choice(abcd) for _ in range(length)) for _ in range(10000): s random_string(random.randint(1, 20)) if brute_force(s) ! longest_palindrome(s): print(mismatch:, s, brute_force(s), longest_palindrome(s)) break这种对拍在笔试准备阶段价值极大因为很多边界问题靠人脑是很难想全的但机器能在一万次随机测试里帮你找到最小反例。把这三个解法变为本能我自己的经验是回文子串这块真正有用的不是背下所有代码而是理解“回文由中心生长”这个直觉。有了这个直觉中心扩展法你可以闭着眼写动态规划只是在给它套一张状态表马拉车则是给同一件事加了一个对称性的缓存。三者是一脉相承的。最后分享一个刷题小习惯每道题提交通过后不要急着开下一题花两分钟想想“如果把输出从长度改成子串本身代码改哪里”“如果字符串变长十倍现有解法还撑得住吗”。这种追问比多做两题更有复利效应。HJ85 这道题做透了回文家族的题你都会轻松很多。
