最长回文子串全解析：从暴力到Manacher的进阶之路

今天晨起刷题看到LeetCode每日一题又轮到第5题“最长回文子串”挺有感触。这道题我第一次做的时候暴力解法直接超时后来才一点点把中心扩展、动态规划、Manacher都过了一遍算是彻底吃透了。今天正好借这轮每日一题把这道题从暴力到最优解的完整路径拆一遍也聊聊每种解法背后的思考过程。如果你正在刷LeetCode热门100题或者刚进字符串专题这篇文章应该对你有用。另外多说一句这道题算得上是回文类题目的“母题”后面遇到的回文链表、回文对、回文子序列思路多少都跟它沾边。所以今天这篇会讲得细一点宁可啰嗦也要让你看完能自己写出来。1. 今天的题为什么是它最长回文子串在面试里的分量1.1 每日一题带来的节奏感比题目本身更值钱身边不少朋友问过我LeetCode每日一题到底值不值得跟。我的结论是值得但别把它当成打卡任务而是当成一个“算法日历”。官方出题不是随机丢一道题过来它会有意识地覆盖不同数据结构和算法板块。你今天刷数组明天可能就轮到二分后天又跳到DP长期跟下来你会在不知不觉中把热门题型都过一遍。这种覆盖面靠自驱刷题其实是很难做到的因为人总会下意识刷自己擅长的部分而每日一题没有这种选择性。最长回文子串被安排在今天的每日一题上我一点都不意外。字符串专题里回文是出现率最高的考点之一而第5题又是回文题的经典代表。这道题的好处在于它一道题就可以串起多种解题思路暴力枚举、中心扩散、区间DP、Manacher线性算法。如果你只是想“把题做出来”那中心扩展法就够了但如果你想把算法分析能力往上提一档这道题值得反复做。1.2 回文这个考点背后的三个层次面试官为什么这么爱考回文回文串的判定本身很简单不就是正着读反着读一样嘛。但一旦问“最长回文子串”难度就上来了。它至少考三样东西你能不能分析暴力解法的复杂度并且说清楚它为什么不可行。你知不知道回文串“去掉首尾还是回文”这个性质能不能把它变成动态规划的状态转移。你在面对n1000的约束时能不能快速判断用O(n^2)的解法够不够还是需要更激进的优化。很多题解喜欢直接甩Manacher的模板一眼看上去很高端但面试官真正想看的是你的思考路径而不是背模板。所以今天这篇我会先讲暴力解法为什么必挂再讲中心扩展法怎么省掉重复计算然后讲DP填表顺序里那些坑最后才聊Manacher这种线性解法到底该不该学。2. 暴力解法的三维复杂度回文判断的重复计算到底有多严重2.1 暴力枚举的完整过程暴力解法的思路是最直观的把所有子串都枚举出来然后逐个判断是不是回文。枚举子串需要两层循环起点i从0到n-1终点j从i到n-1子串的数量是O(n^2)。每拿到一个子串判断它是不是回文最坏情况下要从两端往中间逐个比较这一步又是O(n)。三层套在一起总复杂度就是O(n^3)。拿sbabad来举例。这个字符串的所有子串里有bab、aba这种长度为3的回文也有a、b这种单字符回文。暴力方法会把每一个子串都检查一遍哪怕它们之间有大量重复比较。比如判断bab的时候要比较s[0]和s[2]判断baba的时候又从头开始比较。两次判断之间没有任何信息共享这就是暴力解法最吃亏的地方。2.2 重复计算为什么是致命伤你可能觉得O(n^3)也不算特别吓人我们来算笔账。当n100时最坏情况要比较大约100万次这个量级在普通电脑上确实能跑但LeetCode的字符串长度经常给到1000。n1000时O(n^3)意味着大约10亿次字符比较这就不是“稍微有点慢”了而是直接打到超时。更关键的是这里的重复是非常明显的。假设你已经知道s[1:3]ab不是回文那么在判断s[0:4]baba的时候你其实不需要再重新检查中间的ab因为“去掉首尾之后是不是回文”这个信息完全可以被内层子串复用。暴力解法没有这种复用机制所以它做的很多工作都是无用功。2.3 暴力解的唯一价值是建立基线我建议你第一遍写这道题的时候先老老实实写个暴力版本哪怕知道它提交不过。为什么因为写暴力能帮你建立一个清晰的基线你会在编辑器里亲眼看到它怎么超时然后你才会真正理解为什么后面那些优化是有必要的。如果你一上来就背中心扩展法的代码你不一定理解它到底省掉了什么。还有一种情况暴力解法也不是完全没用。如果面试时遇到一道很偏的题你一时想不出最优解先给一个暴力解法再说明它的复杂度然后表示“我接下来会尝试用DP优化”这种沟通方式在面试官眼里是加分项。怕的是你连暴力都写不利索那后面就无从谈起了。3. 中心扩展法把回文当作以某个点为中心的对称扩散3.1 为什么回文一定有中心中心扩展法的核心观察是任何回文串都有一个中心。奇数长度的回文中心是中间那个字符比如racecar的中心是e偶数长度的回文中心是中间两个字符之间的空隙比如abba的中心在bb之间。理解这两个不同形态的中心是写出正确代码的关键。于是枚举中心就成了一个自然的方向。一个长度为n的字符串一共有n个字符中心还有n-1个字符间隙中心加起来就是2n-1个中心。对每个中心向左右两侧扩展只要左右字符相等就把半径扩大一格直到不能扩展为止。过程中记录最长的回文起点和长度。这个思路本质上就是“从内向外生长”把每个可能的回文中心都当作种子看它最远能长多大。它之所以比暴力快是因为它只用考虑回文这一个维度不会去检查那些根本不可能成为回文的子串。3.2 Python实现中心扩展法的完整代码def longestPalindrome(s: str) - str: if not s: return start, max_len 0, 1 def expand(left: int, right: int): nonlocal start, max_len while left 0 and right len(s) and s[left] s[right]: cur_len right - left 1 if cur_len max_len: max_len cur_len start left left - 1 right 1 for i in range(len(s)): expand(i, i) # 奇数长度回文中心是字符本身 expand(i, i 1) # 偶数长度回文中心是字符间隙 return s[start:start max_len]代码不长核心就是expand这个辅助函数。每次从左指针和右指针开始只要不越界且两个字符相等就同时往左右扩展。如果当前子串比之前记录的最长回文还长就更新start和max_len。3.3 两个容易踩的坑第一个坑是边界判断顺序。while条件里必须先把left 0和right len(s)写在前面再写s[left] s[right]。Python的and是从左到右短路求值的如果先判断字符相等而left已经小于0就会直接抛IndexError。这个错误我在初学的时候踩过很多次后来形成肌肉记忆才改过来。第二个坑是max_len和start的更新时机。我见过不少同学在expand函数里返回一个子串然后再跟当前最优值比较这样写也能工作但每扩展一次就要切片一次性能会打折扣。用nonlocal变量在扩展过程中持续更新是最干净的做法。中心扩展法的时间复杂度是O(n^2)空间复杂度是O(1)因为每个中心最多扩展n次一共2n-1个中心。实测在n1000的用例下毫秒级就能出结果比暴力快了不止一个数量级对于绝大多数面试场景已经完全够用了。4. 动态规划填表顺序为什么必须按子串长度从小到大4.1 从“去掉首尾”到状态转移中心扩展法已经能通过所有测试用例了为什么还要学动态规划因为回文串有一个很漂亮的性质如果s[i1:j-1]是回文并且s[i]s[j]那么s[i:j1]一定也是回文。这个性质可以直接改写成状态转移方程。设dp[i][j]表示子串s[i:j1]是否为回文那么dp[i][j] (s[i] s[j]) and dp[i1][j-1]这个方程的意思很简单一个长回文去掉首尾两个字符之后剩下的一定还是回文。反过来如果首尾两个字符相等且中间的短子串是回文那当前这个长子串就是回文。4.2 初始化长度1和长度2的边界转移方程里有个问题当j-i1等于2的时候dp[i1][j-1]会指向一个不存在的区间比如dp[0][1]会依赖dp[1][0]。所以在写代码时要把长度1和长度2的情况单独处理。长度1的子串也就是单个字符一定是回文所以dp[i][i]True。长度2的子串只要两个字符相等就是回文。代码里可以用一个if length 2来兜住这个边界逻辑更清晰。4.3 填表顺序的坑为什么不能按i从小到大这是DP解法最容易出错的地方。如果按i从小到大、j从大到小去枚举计算dp[0][3]的时候会用到dp[1][2]而dp[1][2]此时还没被算出来结果就全错了。正确的填表顺序是先枚举子串长度length从2到n再枚举起点ij就是ilength-1。这样在计算长度为length的dp值时它依赖的dp[i1][j-1]长度是length-2已经在上一轮循环里算好了。说白了回文DP的依赖方向是“短子串推导长子串”所以填表顺序必须跟这个依赖方向一致。你不可能先算长的再算短的那样跟没算一样。4.4 Python实现DP解法的完整代码def longestPalindrome(s: str) - str: 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 length 2: 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]代码本身不难难的是想清楚填表顺序。理解了上面那个“先枚举长度”的坑之后这段代码基本就是体力活了。4.5 空间优化把O(n^2)降到O(n)看dp转移方程可以发现计算长度为length的dp值时只用到了长度为length-2的上一轮结果再早的结果完全用不上。所以空间上可以优化不需要保留完整的二维表用两个一维数组滚动更新即可。不过我在面试中一般会先写O(n^2)空间的版本因为可读性最强。如果面试官追问“能不能降低空间复杂度”我再现场改写成滚动数组。这样既展示了你对DP的理解又不会一上来就把面试官绕晕。5. Manacher算法一个线性解法的读法以及要不要在面试中写5.1 预处理把所有回文统一成奇数长度Manacher算法的思路一句话总结就是利用回文的对称性避免对每个中心都从头扩展。它首先对字符串做预处理在每个字符之间以及首尾都插入一个特殊字符比如#。这样“abc”会变成“#a#b#c#”原来奇数长度的回文和偶数长度的回文在预处理串里都变成奇数长度了。为什么这很重要因为偶数长度的回文中心落在字符间隙上处理起来不方便。插入分隔符之后所有中心都落在一个具体的字符上代码逻辑就统一了。5.2 p[i]数组和对称性复用Manacher算法维护一个数组p[i]表示以t[i]为中心能扩展到的单侧长度。同时维护center和rightright表示当前所有回文覆盖到的最右边界center就是覆盖到right的那个回文的中心。遍历到i时如果i在right的左边就可以利用i关于center的对称点mirror来给p[i]一个初始值。因为这两个对称点所处的回文环境是一样的p[i]至少是min(right-i, p[mirror])。这个初始值省掉了不少重复扩展然后继续尝试往外扩看能不能突破right。这个过程第一次看容易绕晕我自己的理解方式是把它类比成“照镜子”你已经知道左边一大段是回文了右边还没扫描到的地方跟左边是对称的那就不用一个个从头比较直接继承左边已经算好的信息。5.3 Python实现Manacher算法的完整代码def longestPalindrome(s: str) - str: if not s: return t # #.join(s) # n len(t) p [0] * n center 0 right 0 max_center 0 max_len 0 for i in range(n): if i right: mirror 2 * center - i p[i] min(right - i, p[mirror]) 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] if p[i] max_len: max_len p[i] max_center i start (max_center - max_len) // 2 return s[start:start max_len]最后一步就是通过max_center和max_len反推出原始字符串里的起点。这里的max_len对应的是原始回文串的长度start的计算公式在预处理串和原始串之间做了坐标映射不要自己瞎推直接按这个公式来最稳。5.4 到底要不要在面试里写Manacher我的态度很明确除非面试官明确考的是字符串算法并且追问“有没有更优解”否则不要一上来就写Manacher。原因有两点。第一Manacher的代码虽然只有30行左右但逻辑复杂度远高于中心扩展法面试时手写很容易在p[i]的初始化和边界更新上出bug写了半天还跑不对反而影响整体印象。第二面试官通常更看重你能否清晰表达思路而不是背模板。中心扩展法O(n^2)的时间复杂度在n1000的约束下已经完全够用面试官不会因为你不写Manacher就否定你。不过如果你目标明确比如在刷竞赛题或者面算法岗我还是建议理解一下Manacher。它把“利用对称性减少重复计算”这个思想体现得淋漓尽致这种思想在KMP、Z算法里也能看到学会了是好事。6. 从一道题到一类题热词背后的方法论迁移6.1 目标和搜索怎么迭代成DPLeetCode热门题里有一道“目标和”跟最长回文子串看起来毫不相关但底层的进化路径很像。它一开始可以写DFS每个数字要么加要么减两条路走到底看最后能否得到target。直接DFS会超时因为状态重复太多。这时候你发现可以用记忆化搜索再进一步简化成01背包DP把问题转化成“选一部分数字加负号让总和等于某个值”的计数问题。对比一下就能发现回文DP是“去掉首尾”这个性质驱动出来的目标和DP是“加当前数字还是减”这个选择驱动出来的。共同点是都要先明确状态是什么再写转移方程最后处理边界。这就是方法论迁移的基础。6.2 爱吃香蕉的狒狒二分答案的“单调性”另一道热词里很有意思的题是“爱吃香蕉的狒狒”LeetCode第875题。它的本质是求一个最小速度k使得狒狒能在h小时内吃完所有香蕉。这里有个关键观察k越大吃完需要的时间越少这是一个单调函数。所以可以用二分答案每次判断当前速度是否能在h小时内吃完然后缩小搜索范围。Manacher和二分答案之间看起来没什么关系但它们在“先想清楚怎么表示目标再设计算法”这一点上是相通的。Manacher先插入#来统一奇偶二分答案先确定单调性这些预处理和性质分析才是解题真正花时间的地方。很多刷题的人一上来就套模板却忽略了这一步结果到了变体题就卡住。6.3 杨辉三角动态规划最朴素的形态“杨辉三角”是很多人的DP入门题它比最长回文子串更简单但结构非常清晰第i行的第j个数字等于第i-1行的第j-1个数字加上第i-1行的第j个数字。这种“上一行推导下一行”的方式和回文DP的“短子串推导长子串”几乎是同一个套路。我建议你把这些题放在一起刷而不是孤立地刷某一道。最长回文子串、目标和、杨辉三角这三道题看起来毫无关联但它们都在训练同一件事找状态、写转移、卡边界。等你把这三个环节变成肌肉记忆遇到新题就不会慌。6.4 拿到新题先问自己的三个问题最后分享一个我自己的习惯。遇到一道没做过的题我不会急着写代码而是先问三个问题状态是什么我要在一个什么样的表格或维度上做决策。转移是什么从一个更小的状态怎么推出当前状态。边界在哪里初始化哪些值哪些特殊情况要单独处理。最长回文子串的状态是“子串是否为回文”转移是“去掉首尾后是否回文”边界是“长度1总是回文”。目标和的状态是“当前下标和当前总和”转移是“加还是减”边界是“下标走到底时判断总和”。杨辉三角的状态是“当前行当前列的值”转移是“上一行两个值相加”边界是“每行首尾都是1”。这三问想清楚之后一道题的基本框架就出来了剩下的就是细节和调试。刷题这件事说到底不是比谁背的模板多而是比谁能在更短的时间里看清问题的结构。最长回文子串这道题之所以被我反复拿出来讲就是因为它一个题目里塞了好几种结构从暴力到线性每一层都能学到点东西。今天这轮每日一题能轮到它也算是个整理思路的好机会。你如果之前只是草草做了一遍建议隔两周回来再做一次不看题解卡住了再去看。这种做法比一次刷十道题管用。