1. 先看清第 5 题在问什么不是“判断回文”而是“找全部回文中最长的那段”刷 LeetCode Hot 100 的同学应该都有这样的体验第 5 题“最长回文子串”看起来人畜无害毕竟判断一个字符串是不是回文谁都会写——左右两个指针往中间一夹就行。可一旦要求“返回字符串 s 里的最长回文子串”事情就变了你需要在一大堆子串里挑出最长的那段而不是只判断某一小段成不成立。这个区别恰恰就是这道题被放进 Hot 100、并且排得还比较靠前的原因。题目原文很简单给你一个字符串s找到s中最长的回文子串。比如s babad答案是bab或者aba都可以s cbbd答案是bb。注意一个子串必须是连续截取的一段不能跳着选字符。很多人一开始容易把“最长回文子序列”和它搞混子序列才允许跳字符那是另一道题后面我会展开说。那这道题的隐藏考点是什么我认为有三个第一是对称性的理解回文串本质上就是一个关于中心对称的结构第二是重复比较的消除不管你用哪种主流解法核心都是在想怎么少做无用功第三是复杂度的权衡暴力做法能过小数据但数据一旦上千立刻卡死。Hot 100 把它排在第 5 位并不是因为它难到劝退而是因为它把字符串处理、动态规划、双指针思想全串起来了非常适合作为刷题进阶的第一道坎。前置知识其实很少你只需要知道什么是回文串、会写基本的循环和s[i]取字符就行。但如果你想在面试里优雅地讲清楚三种解法中心扩展、动态规划、Manacher那就还需要对“对称信息如何复用”有一个直观的感觉。这篇文章我就按我自己刷这道题的路径来写先从最暴力的思路说起再一步步看到它怎么变成 O(n^2) 的中心扩展又怎么变成一张 DP 表格最后再谈谈真正能做到 O(n) 的 Manacher 算法。每一段我都会把当时的困惑、踩过的坑和现在回头看觉得“早知道就好了”的点放进去。2. 暴力三层循环为什么是“思路陷阱”从 O(n^3) 到 O(n^2) 的关键一步很多人拿到这道题的第一反应是枚举所有子串逐个判断是不是回文取最长的那个。这个思路逻辑上完全正确但它会把复杂度直接拉到 O(n^3)在 LeetCode 上s长度稍微到几百、几千就过不去了。问题不在于“判断回文”本身慢而在于你要判断的子串数量太多了。简单算一笔账一个长度为 n 的字符串子串的起点有 n 种选择终点也有约 n 种选择光枚举所有子串就是 O(n^2) 的规模对每个子串再用双指针判断一次回文每次要 O(n)。乘在一起就是 O(n^3)。n 100 时是 10^6 次操作勉强能忍n 1000 时是 10^9 次已经非常吃力n 10^5 时就是 10^15 次现代计算机也得跑到地老天荒。那么第一个真正有用的优化转折点在哪在于别再枚举“子串”改成枚举“对称中心”。你观察一下任何一个回文串不管它多长都有一个对称中心。奇数长度的回文串中心是正中间那个字符比如aba的中心是b偶数长度的回文串中心是中间两个字符之间的那道空隙比如abba的中心在b和b中间。一个长度为 n 的字符串里能作为对称中心的位置有多少个字符本身有 n 个字符之间的空隙有 n-1 个合起来是 2n-1 个。枚举每一个中心再从这个中心向左右两边同时扩展只要左右字符相等就继续扩直到不能扩为止。每个中心最多扩展 n 次于是总复杂度是 O(2n * n) O(n^2)。这一步的思想其实特别朴素回文串不是“从两端向中间”生成的而是从中心向两边长出来的。你把判断的重点从“这个子串整体是否回文”换成了“以这个位置为中心能长出多长的回文”一下子就把每个子串的重复判断分摊掉了。这也是我觉得暴力和中心扩展之间最本质的分界线——不是代码量的问题而是你有没有意识到“对称中心”才是回文问题的最小单位。解法时间复杂度空间复杂度适合场景暴力枚举子串O(n^3)O(1)只用来理解题意中心扩展O(n^2)O(1)面试首选主解动态规划O(n^2)O(n^2)需要迁移到其他回文题ManacherO(n)O(n)大数据量、追求最优很多教程会把中心扩展当成“面试最推荐写法”原因就在空间上你只需要两个指针做扩展不需要额外开表就可以拿到最优解的同数量级复杂度。动态规划虽然也是 O(n^2)但要开一个 n*n 的二维数组讨论起来多一层负担。所以在面试里我的建议顺序永远是先写中心扩展讲清楚它比暴力好在哪如果时间富余再补一下 DPManacher 可以提思路不一定强求写成代码。3. 中心扩展法面试中的主力解法代码短且空间为 O(1)中心扩展法的实现并不长但很多第一次写的人会在“奇数长度和偶数长度怎么统一处理”上卡住。我的建议是干脆不要试图去统一写一个辅助函数expand(left, right)它接收两个初始下标代表当前中心在哪个位置然后不断向两边扩展。如果回文中心是一个字符就传(i, i)如果中心是字符之间的空隙就传(i, i 1)。这样奇数、偶数天然都覆盖了不需要额外的 if 分支。这里有一个我当年踩过的小坑辅助函数返回的长度到底是什么如果你直接返回right - left 1那是在 while 退出前最后一次合法扩展的位置。但更稳妥的做法是让 while 循环先走到不满足条件然后再返回最终的实际匹配长度。写成代码就是这样def longestPalindrome(s: str) - str: if not s: return n len(s) start, end 0, 0 def expand(left: int, right: int) - int: while left 0 and right n and s[left] s[right]: left - 1 right 1 # 退出 while 时left 和 right 已经越界一位 # 实际匹配长度是 right - left - 1 return right - left - 1 for i in range(n): len1 expand(i, i) # 奇数长度回文 len2 expand(i, i 1) # 偶数长度回文 cur_max max(len1, len2) if cur_max end - start: start i - (cur_max - 1) // 2 end i cur_max // 2 return s[start:end 1]我重点解释一下最后更新start和end的两个公式因为很多人背下来了但不知道为什么。比如expand(i, i 1)表示中心在s[i]和s[i1]之间的那道空隙我们统一用i来代表这个中心的位置。假设最终得到的最长回文长度是cur_max那么这段回文的左端点应该是i - (cur_max - 1) // 2右端点是i cur_max // 2。为什么是这个式子你可以代入两个例子验证。字符串cbbd最长回文是bb长度为 2中心空隙在i 1处。左端点1 - (2-1)//2 1 - 0 1右端点1 2//2 2所以返回s[1:3]正好是bb。再看babad最长回文长度是 3比如i 1时向两边扩展得到bab。左端点1 - (3-1)//2 0右端点1 3//2 2返回s[0:3]正确。这个公式的妙处在于它利用整除的向下取整把奇偶长度统一了。你不需要分情况讨论记住这个式子就行。那有哪些地方特别容易写错我列几个真实遇到的忘记处理空串。如果s 直接返回空字符串别让循环去访问s[0]。把end - start和cur_max比较时要注意end是闭区间的右端点所以当前记录到的长度是end - start不是end - start 1。我第一次写的时候这里多加了 1结果返回的字符串老是长一截。expand内的 while 条件一定要先判断边界比如left 0和right n要写在前否则下标一越界就IndexError。在 Python 里(cur_max - 1) // 2当cur_max是偶数时其实得到的是cur_max / 2 - 1这恰好让左端点往左多让一位当cur_max是奇数时得到的是cur_max // 2。所以它天然兼容两种长度这也是为什么我一直推荐用这个写法而不是分开写 if。说句实在话中心扩展法在面试中已经算“够用且优秀”的答案了。时间复杂度 O(n^2) 在绝大多数笔试和面试场景里都能通过空间复杂度又只有 O(1)你完全可以把更多精力放在为什么它是对的、时间复杂度怎么推导上。如果你只准备一种解法应付这道题我会毫不犹豫推荐它。4. 动态规划解法把“是否回文”变成一张可复用的表动态规划的切入点不太一样它不关注“某个中心能扩展多远”而是用一张二维表dp[i][j]记录“子串s[i..j]是不是回文”。换句话说我们把“每个子串是否是回文”这个问题的答案缓存下来后面再用的时候直接查表。状态转移其实很漂亮。dp[i][j]要成立需要满足两个条件第一s[i]等于s[j]首尾字符相同第二去掉首尾之后剩下的内部子串s[i1..j-1]也必须是回文或者这个子串足够短比如长度是 0 或 1那自然就是回文。写成转移式就是if s[i] ! s[j]: dp[i][j] False else: if j - i 3: dp[i][j] True else: dp[i][j] dp[i 1][j - 1]这里j - i 3这个条件可能有点绕。它表示子串长度j - i 1小于等于 3长度为 1 时左右边界相同同一个字符长度为 2 时两个字符相等就是回文长度为 3 时首尾相等、中间只有一个字符也肯定是回文。所以这三个长度根本不需要查表直接置 True 就行。我之前见过有人写成j - i 2其实和j - i 3完全等价都可以。完整实现如下def longestPalindrome(s: str) - str: n len(s) if n 2: return s dp [[False] * n for _ in range(n)] for i in range(n): dp[i][i] True start 0 max_len 1 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 j - i 3: dp[i][j] True else: dp[i][j] dp[i 1][j - 1] if dp[i][j] and length max_len: start i max_len length return s[start:start max_len]这里有一个初学者特别容易踩的坑为什么外层循环要先按length枚举再枚举起点i原因是dp[i][j]依赖的是dp[i1][j-1]也就是长度短 2 的那个子串。如果你按常规的i从前往后、j从后往前的顺序填表可能你在算dp[i][j]的时候dp[i1][j-1]还没被算出来。所以必须保证“更短的子串先被更新”最直接的办法就是外层枚举长度内层枚举起点。当然也不是没有别的遍历方式。你还可以让i从n-1往0走内层j从i1往n走这样dp[i1][j-1]所在的下一行已经算过了也能保证正确。很多题解里的写法是前者面试时只要能讲清楚“依赖顺序”这一点两种写法都是可以接受的。动态规划解法的优点是思路统一尤其适合变种题。比如后面要统计回文子串的个数用 DP 表格可以顺手计数比如最长回文子序列那更是直接套区间 DP 的框架。缺点是空间复杂度高O(n^2) 的二维数组在n 10^5时根本开不出来。所以如果你只为了做 LeetCode 5 这一道题DP 不如中心扩展省事但如果你想通过这一题顺便打通后面好几道回文题DP 是值得熟练掌握的。空间优化可以做到一维滚动数组因为dp[i][j]只依赖更短的区间结果。但我的个人建议是面试时不要轻易把代码优化成滚动数组因为一旦你开始“滚动”你就不再保留所有子区间的答案了如果题目要求最后输出具体子串记录起始位置会变得特别容易出错。先用二维表把正确性讲清楚如果面试官追问能不能降空间你再提“可以用滚动数组优化到 O(n)但为了保持可读性先不写了”这是一个很得体的应对方式。5. Manacher线性时间算法究竟“快”在哪儿如果面试官继续追问或者笔试数据量特别大比如长度达到 10^6O(n^2) 的算法就扛不住了。这时候就需要 Manacher 算法它能把找最长回文子串的复杂度降到 O(n)。我第一次看到这个算法的时候觉得它像魔法明明每个中心都需要向两边扩展怎么可能线性完成后来才明白它本质上是在“利用已经算好的对称信息做跳跃”而不是从头扩展。先看预处理。Manacher 会把原始字符串扩展成一个所有回文中心都变成“单一字符位”的形式在字符串的首尾和每个字符之间插入一个特殊字符。常见做法是t # #.join(s) #比如babad就变成#b#a#b#a#d#。为什么要这么干因为原来的字符串里奇数长度回文的中心是字符偶数长度回文的中心是空隙两种中心类型不一致。插入#之后所有回文串在t里都变成了奇数长度中心位置要么是原始字符、要么是插入的#统一处理起来非常方便。更精细的写法会在首尾再加上^和$用来当哨兵防止 while 扩展的时候频繁判断数组越界t ^# #.join(s) #$接下来定义数组P[i]它表示以t[i]为中心、往两边扩展时能匹配到的不含中心本身的半径长度。然后我们维护两个关键变量center和right。right表示当前扫描过程中所有已知回文串里能到达的最右边界center就是产生这个最右边界的那一个中心。这两个变量是整个算法的灵魂。Manacher 的核心复用逻辑可以描述成一句话如果当前枚举的中心i还在已知回文区间内部也就是i right那i关于center的镜像位置mirror 2 * center - i的半径早就已经算过了P[i]可以直接取min(P[mirror], right - i)作为初始值。这个初始值不是乱猜的它来源于回文的中心对称性在center这一圈回文里i和mirror完全对称所以mirror能匹配的字符i大概率也能匹配。但镜像的半径可能超出center已知回文的左边界超出部分不能保证所以我们用right - i把它截断。打个比方这就像你抄别人已经做好的作业镜像点mirror已经把左半边的情况摸清楚了你想知道i这边最少是多少可以直接“抄”过来但抄的范围不能超过已知答案的边界。超出边界之后还得老老实实自己扩展验证。这也是我经常推荐学生用“抄作业但不超过答案边界”来理解 Manacher 的原因非常直观。完整代码我贴一个能直接跑的版本def longestPalindrome(s: str) - str: t #.join(^{}$.format(s)) n len(t) p [0] * n center 0 right 0 for i in range(1, n - 1): if i right: mirror 2 * center - i p[i] min(right - i, p[mirror]) while 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_len 0 center_idx 0 for i in range(1, n - 1): if p[i] max_len: max_len p[i] center_idx i start (center_idx - max_len) // 2 return s[start:start max_len]这里的p[i]表示的是“不含中心本身的扩展半径”所以最终最长回文子串的原始长度和p[i]是有对应关系的。最后计算start的时候用(center_idx - max_len) // 2很多第一次写的人会漏掉这个细节算出来是负数或者偏差一位。我建议自己拿babad和cbbd各跑一遍把t数组的下标写出来你就能很清楚它为什么成立。那为什么说它是线性时间关键在于right是只增不减的。while 循环每扩展成功一次right就会往右推进一次整个算法过程中right从 0 最多推进到 n所以所有 while 操作的总次数是 O(n)。再加上每个下标本身只遍历一次总复杂度就是 O(n)。这也是 Manacher 最漂亮的地方它把原本每个中心都要“从头扩展”的 O(n^2) 工作借助对称性压缩成了 O(n)。不过我还是要说一句实在话Manacher 属于那种“原理懂了很好但代码细节特别容易写岔”的算法。如果你在面试里能完整写出中心扩展法并且能大概讲清楚 Manacher 的right、center、mirror三位一体的思路已经足够拿一个不错的评价。如果面试官要求你现场写完整的 Manacher而且你一时写不顺坦诚地说“这个算法我更多是理解思路边界和下标细节需要再推一下”往往比硬着头皮写一个出错的版本更好。6. 从这道题延伸开的高频变体与刷题节奏建议最长回文子串不是孤立的题。刷完它你会发现在 LeetCode 和面试题里有一批和它长相相似、解法却微有不同的题目。提前搞清楚它们之间的差异比单纯背一道题的代码有用得多。最直接的变体是LeetCode 647 回文子串个数。它问的不是最长回文子串而是字符串里一共有多少个回文子串。这道题用中心扩展法非常顺手因为你每从一个中心向外成功扩展一次就相当于发现了一个新的回文子串直接计数就行。如果你非要先算完所有回文子串再去统计那就绕远了还会多开一个二维数组。这就是中心扩展法优于动态规划的一个典型场景。另一个常见变体是LeetCode 516 最长回文子序列。注意“子序列”和“子串”的区别子串必须连续子序列可以跳着选字符。一旦允许跳字符中心扩展法和 Manacher 就都不能用了因为你没法再靠“向两边逐字符比较”来判断对称关系。这类题要用区间 DPdp[i][j]表示s[i..j]中最长回文子序列的长度转移时看s[i]和s[j]是否相等如果相等就是dp[i1][j-1] 2不相等就取max(dp[i1][j], dp[i][j-1])。这种“连续 vs 不连续”的判断是我觉得回文题里最容易混淆的地方。面试中还经常出现一种小变体给你一个字符串问能否通过最多删除一个字符让它变成回文。这道题不需要动态规划双指针从两端往中间扫第一次遇到左右不相等的时候检查跳过左边或者跳过右边之后剩下的内部子串是否是回文即可。它看起来也是回文题但解法已经完全不是一回事了。所以你看回文这个主题底下其实藏着好几种问题模型搞懂“连续”和“不连续”、搞懂“求最长”和“判断可行”要比单纯刷题有用得多。回到 LeetCode 5 本身我建议的刷题节奏是这样的第一天先把中心扩展法写熟练能用它解释清楚为什么是 O(n^2)第二天可以自己推导动态规划版本重点理解遍历顺序第三天或者后面有空再去啃 Manacher。不用急着一天之内拿下所有解法那样很容易变成“背代码”而不是“理解算法”。我刷这道题前后三遍每一遍都有新感受第一遍惊险 AC 但没理解为什么中心扩展能替代暴力第二遍写 DP 时理解了子区间递归的依赖第三遍看 Manacher 才真正体会到“对称信息复用”这个底层思维的价值。最后分享一个小经验遇到“最长 XX 子串/子序列”类的问题先别急着套模板先问自己三个问题——要求连续还是不连续要求返回内容还是只返回长度数据规模有多大把这三个问题想清楚再选解法基本不会走偏。