1. 遇到最长回文子串先别急着写暴力循环1.1 这个问题到底在问什么“最长回文子串”是字符串处理领域的入门级经典题几乎每个算法面试题库里都有它的身影。题目描述很简单给定一个字符串s找到其中最长的回文子串。所谓回文就是正着读和倒着读都一样比如aba、racecar、上海自来水来自海上。但简单描述背后藏着一个容易混淆的概念子串和子序列是两回事。子串要求字符在原字符串中连续子序列只需要相对顺序一致即可。最长回文子串要求的是连续的一段这直接决定了后面要用什么算法来处理。很多朋友一上来就想用动态规划结果把状态定义成了“子序列”的模型方向就偏了。输入边界也值得事先想清楚字符串可能为空、只含单个字符、全是大写/小写字母、全部字符相同甚至包含空格和标点。这些极端情况不是刁难而是判断一个实现是否健壮的标尺。我见过不少人在白板上写得飞快一跑测试用例就挂在和a上都是因为没提前规划边界条件。1.2 为什么这个问题值得反复刷最长回文子串之所以成为高频题不是因为它本身有多难而是它一个题目串起了暴力枚举、区间动态规划、双指针、马拉车算法等多个层级的方法。从最朴素的 O(n3) 写法一步步优化到 O(n) 的 Manacher 算法这个过程中的思维递进比题目本身更有锻炼价值。另外它在实际工程里也有应用场景。文本相似度判断、基因序列比对、日志中的重复模式分析甚至某些加密算法的辅助校验都会用到回文匹配的思想。虽然日常业务里直接写一个 Manacher 算法的机会不多但理解它的对称性优化思路对以后看复杂的字符串匹配代码会很有帮助。我自己在带新人时习惯让他们先把暴力解写出来不追求效率追求“正确”。写完暴力解再问三个问题这个解法的复杂度是多少能不能把重复比较的结果存下来存下来之后能不能进一步压缩这篇文章就按照这条思路走一遍每一步都解释清楚“为什么要这么干”。2. 从暴力解到中心扩散先建立直观手感2.1 暴力枚举的代价与思考起点最直观的解法是枚举所有子串再逐个判断是否回文。伪代码如下def longestPalindrome_bruteforce(s): n len(s) ans for i in range(n): for j in range(i, n): sub s[i:j1] if sub sub[::-1] and len(sub) len(ans): ans sub return ans这段代码很好理解枚举起点i、枚举终点j、提取子串、反转比较。逻辑上不会出错但复杂度是 O(n3) 的——枚举子串用了两层循环每次反转比较又要 O(n) 时间。当字符串长度达到几百个字符时程序还能忍受一旦到了 10 万量级这样的代码基本就跑不完了。写这种算法的时候我建议在头脑里建立一个数据规模对照表O(n2) 算法大概能处理 10^4 级别的数据O(n3) 的算法超过 500 就要开始担心性能。LeetCode 这类平台上常见测试数据的长度上限能达到 1000 左右暴力解法在边界用例上会非常吃力。暴力解的真正价值是帮助我们意识到一个关键事实判断回文时内层比较做了大量重复工作。比如先判断了abcdcba是回文紧接着判断bcdcb时中间那段完全重叠却被重新比较了一遍。这种重叠子结构正是后续优化要抓住的核心。2.2 中心扩散从“比对整个串”到“从中心向外生长”比暴力枚举更符合直觉的写法是把回文看作“从中心向两边对称扩展”。一个回文串一定有一个中心点中心要么是一个字符对应奇数长度如aba的中心是b要么是两个字符之间的空隙对应偶数长度如abba的中心在bb之间。于是我们可以枚举每一个可能的中心点然后向左右两侧扩展只要左右字符相等就继续扩不相等就停止。总共有2n-1个中心n个字符本身加n-1个字符间隙。每个中心的扩展过程最多走遍半个字符串所以整体复杂度是 O(n2)。def expand_around_center(s, left, right): while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 return s[left1:right] def longestPalindrome_center(s): if not s: return res for i in range(len(s)): odd expand_around_center(s, i, i) even expand_around_center(s, i, i1) res max(res, odd, even, keylen) return res这段代码堪称“手写题最佳模板”因为它不需要额外数组只用两层循环就完成了所有工作。面试时写这个方法通常比写动态规划更容易让人理解也更容易在十分钟内写对。中心扩散和暴力枚举的核心区别在于暴力解法站在区间外面审视整个子串中心扩散站在回文的中心向外生长。“判断”变成了“生长”从而把大量重复的中间比较天然地合并在一起这个转变是后面理解 Manacher 算法的铺垫。2.3 两种 O(n2) 方法的对比与选择动态规划解法也能做到 O(n2)但空间复杂度是 O(n2)因为需要一张二维表来记录任意[i, j]区间是否回文。中心扩散的空间复杂度只需要 O(1)。这就是为什么在实际编码中尤其是限制内存的笔试环境里中心扩散往往比二维 DP 更受欢迎。方法时间复杂度空间复杂度编码难度面试推荐度暴力枚举O(n3)O(1)极易低动态规划O(n2)O(n2)中等中中心扩散O(n2)O(1)易高ManacherO(n)O(n)较难高进阶不过动态规划的思路也有不可替代的价值它把回文判断转化成了区间递推问题这种二维 DP 的建模方式在后续很多字符串题比如编辑距离、最长公共子串里都会用到。所以即使中心扩散更简洁我仍然建议你把 DP 版本写一遍深入理解“依赖关系”是怎么形成的。3. 动态规划解法把回文判断变成查表3.1 状态定义与状态转移的由来动态规划的第一步永远是定义状态。这里我定义dp[i][j]表示子串s[i:j1]即从下标 i 到 j 的一段是否为回文。显然单个字符一定是回文dp[i][i] True。两个相邻字符如果相等则dp[i][i1] True。接下来是关键递推对于长度大于 2 的区间如果s[i] s[j]且s[i1:j]是回文那么s[i:j1]就是回文。写成转移式dp[i][j] (s[i] s[j]) and dp[i1][j-1]这个递推式的直觉很清晰两头相同剥掉一层后里面还是回文那整个串必定是回文。这种思路有点像扒洋葱从外往里一层层验证。3.2 表怎么填按长度遍历而非按起点遍历实现 DP 时最常见的错误是双重循环都从 0 开始往上走结果在用到dp[i1][j-1]时发现还没算出来。原因在于dp[i][j]依赖的是更短区间[i1, j-1]而不是更长的区间。所以外层循环必须按子串长度从小到大内层循环枚举起点。def longestPalindrome_dp(s): n len(s) if n 2: return s dp [[False] * n for _ in range(n)] start, max_len 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 j - i 3: dp[i][j] True else: dp[i][j] dp[i1][j-1] if dp[i][j] and length max_len: start i max_len length return s[start:start max_len]注意j - i 3这个判断它覆盖了长度等于 2 和 3 的情况。长度 2 时只要s[i] s[j]就成立长度 3 时剥掉两端只剩一个字符天然是回文。很多读者把这里写成j - i 2效果一样但加上注释更清晰。3.3 DP 的短板与适用场景DP 解法美观但 O(n2) 的空间在长字符串下确实不够优雅。假设字符串长度为 5000需要开辟 2500 万个布尔值约 25MB 内存在某些嵌入式或移动端环境里已经算很大开销。而且填表过程本质上还是在枚举区间时间复杂度并没有实质下降。所以我的建议是DP 版本属于“必须会写”的经典建模练习但现场解题时优先选择中心扩散除非题目要求展示多种解法或者空间不受限制。学习阶段三个版本都写一遍你才能真正体会到为什么 Manacher 是“屠龙刀”。4. Manacher 算法利用对称性把复杂度压到 O(n)4.1 预处理统一奇偶的巧思中心扩散需要同时考虑奇数长度和偶数长度两种中心这带来了额外分支。Manacher 算法的第一个关键步骤就是通过插入分隔符把奇偶问题统一起来。比如在字符串aba的每个字符之间和首尾都插入#得到#a#b#a#原始串abba变成#a#b#b#a#。经过处理后原串的所有奇偶回文在新串里都变成了奇数长度的回文且都有一个明确的中心分隔符或字符。这样只需要处理“奇数长度回文”这一种情况代码里少了很多if/else分支。这是整个算法最精巧的第一步。有个细节值得记住处理后的新串长度为2n 1总是奇数。回文半径的长度与原始回文长度也对应起来了——新串里某个中心的回文半径减去 1正好等于原串中以该位置为中心的回文子串长度。这个对应关系是最后还原答案的关键。4.2 回文半径数组与镜像加速接下来引入两个概念center是当前已知最靠右回文串的中心right是这个回文串的右边界p[i]表示以位置 i 为中心的回文半径包含中心本身。核心遍历过程中我们维护不断更新的center和right。当遍历到位置 i 时如果 i 还位于 right 以内那么它一定有个对称点mirror 2 * center - i。因为回文串左右对称p[i]至少可以直接复用p[mirror]的结果但不能超过right - i这个边界。这一步就是算法的“加速”所在——很多位置的回文半径不需要从头扩展直接通过对称性查出来。def manacher(s): t # #.join(s) # n len(t) p [0] * n center 0 right 0 max_len 0 center_index 0 for i in range(n): if i right: p[i] min(p[2 * center - i], 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 if i p[i] right: right i p[i] center i if p[i] max_len: max_len p[i] center_index i start (center_index - max_len) // 2 return s[start:start max_len - 1]这段代码里最关键的一行就是p[i] min(p[2*center-i], right-i)。初看时会觉得绕但拆开想就明白左边的候选值是镜像位置的回文半径右边是保证不越过当前已知右边界。取两者较小值是为了不违反“回文整体对称”的前提。之后再用while循环尝试继续扩展因为复用结果只是跳过了确定的部分剩下的部分仍然可能往外扩。4.3 正确性直觉为什么这不算是“又一种中心扩散”有人会问Manacher 不还是有一个while扩展循环吗跟中心扩散有什么区别区别在于扩展次数。中心扩散每个位置都从头开始扩最坏情况下每个位置要扩到字符串末端而 Manacher 里一旦某个中心确定了右侧最远边界后续位置就能直接复用先前计算的结果while循环只在未知区域才真正工作。可以这样理解中心扩散像每个工人都要从自己起点挖一条隧道互不协作Manacher 等于先派出一支先锋队探出最远边界后续工人只在先锋队没探过的地方继续挖。因为每个位置最多被扩展过一次总体复杂度降到 O(n)。这也是不少教材里说“Manacher 是优化过的中心扩散”的原因。4.4 性能直觉到底快了多少在长度 10 万的字符串上中心扩散在最坏情况下要执行约百亿次字符比较而 Manacher 的字符比较次数大约是线性量的常数倍几百万次以内就能完成。这个差距在实际演示中非常直观。我做过一次简单测试用一个全由a组成的长度 2 万字符串中心扩散版本跑了约 12 秒Manacher 跑完一轮只需要几十毫秒。这种极端数据对中心扩散极不友好但对 Manacher 来说最坏情况和平均情况几乎一样。不过Manacher 也不是完全没有代价。它需要额外保存一张回文半径表空间 O(n)且预处理插字符号后的长度是原始长度的两倍多。工程上如果数据规模不大直接用中心扩散完全没问题只有当你确定字符串会很长且需要频繁调用才值得引入 Manacher。5. 边界条件与面试实战把算法从“背得出”变成“写得稳”5.1 必须提前想清楚的边界用例无论用哪种算法边界条件都能测试出你对代码的掌控力。我习惯在写代码前先列出下面这些用例然后在纸上快速走一遍逻辑空字符串正确输出。单字符a正确输出a。双字符ab正确答案是a或b任选一个即可。双字符aa正确答案是aa。全相同字符aaaa最长回文就是整个串。回文在字符串最左端或最右端比如abac或caba。这些用例看起来简单实际踩坑的次数往往超出预期。比如中心扩散写法里如果没有正确提取s[left1:right]很容易造出下标越界DP 方法里如果忘记初始化长度 1 的表项整个递推就会出错。5.2 面试时的表达顺序与加分细节如果面试官让你写最长回文子串我不建议一上来就写 Manacher。更稳妥的做法是先说出“暴力解是 O(n3)太慢”然后写出中心扩散或 DP让对方看到你熟悉基础方法等对方追问“还能不能再优化”再展示 Manacher。这个顺序展现了层层递进的思考过程比直接甩出最终答案更有说服力。写 Manacher 时注意每一步都要能讲出“为什么”。比如插入分隔符是为了统一奇偶长度维护center和right是为了记录已知的最靠右回文边界复用p[mirror]是因为回文的对称性。最好给自己留一句口语化的总结“本质上是利用回文的镜像性质减少重复扩展次数。”5.3 我踩过的一些实际坑第一预处理后的下标换算。新串的坐标和原串坐标不是一一对应的(center_index - max_len) // 2这个公式我一开始总是记反。我的记忆方法是回文半径p[i]里包含分隔符的长度原串起点在新串中是center_index - p[i] 1再除以 2 就是因为每个原字符旁边都插了一个#。第二判定中心时容易忽略“中心是分隔符”的情况。比如bb预处理后是#b#b#真正回文中心是中间的#而不是某个b。如果代码里漏掉了对分隔符作为中心的考虑偶数长度的回文就会全部漏掉。这也是为什么我推荐 Manacher 模板而不是手写特判。第三不要为了炫技强行上 Manacher。如果字符串长度只有几百中心扩散跑的比 Manacher 还快因为 Manacher 预处理要额外遍历一次字符串并分配较大数组。算法选型永远要结合数据规模不是复杂度越低就越好。5.4 扩展思考从最长回文子串到回文子串数量学会了最长回文子串可以顺手练习一个变体给定字符串求它总共有多少个回文子串。中心扩散的思路同样适用只需要在扩展成功时累加计数即可。LeetCode 上对应的题目是“Palindromic Substrings”本质上和最长回文子串是姊妹题非常适合用来检验自己是否真正理解了回文中心的枚举方法。如果还想进一步挑战可以搜索“最长回文子序列”它与子串的区别在于字符不必连续解法会回到二维动态规划的经典模型。两个问题放在一起对比做能帮你把“子串”和“子序列”这对概念彻底吃透。我自己的习惯是每学一个算法就在 LeetCode 上找两三道同类变体题做实战。最长回文子串学完之后我选了回文子串数量、分割回文串、最长回文子序列三道题连续刷了一周。刷完的最大感受是中心扩散的“枚举中心”思想在很多回文类题目里都可以复用而 Manacher 的正确打开方式是在你彻底理解了普通解法之后再加成它是一把剪枝利器不是一个黑盒模板。