1. 先把这道题彻底读透最长回文子串到底在考什么1.1 题目本质与解题目标LeetCode Hot 100里的第5题“最长回文子串”我刷了不止一遍每次面试前都会重新过一下。这道题表面上是让你在一个字符串里找最长的回文子串比如babad里答案是bab或abacbbd里答案是bb。本质上考的是三件事你能不能快速识别回文的对称结构、能不能把重复的比较过程优化掉、以及你手里的算法工具箱里到底有几套方案。很多初学者一上来就暴力枚举所有子串再逐个判断是否回文字符串一长直接超时。这道题真正的门槛不在“会不会判断回文”而在“能不能用合理的复杂度把最长那个找出来”。面试官拿这道题出来基本是想看你对字符串问题的敏感度以及你能不能从 O(n³) 一步步优化到 O(n²) 甚至 O(n)。适合看这篇内容的人很明确准备算法面试的开发者、在Hot 100里刷题刷到这道题卡住的新手以及想系统补一下回文串三种解法中心扩展、动态规划、马拉车的老手。我会把三种方案全部拆开讲包含代码、复杂度、边界坑以及我实际刷题和面试时踩过的真实教训。1.2 暴力法为什么注定被淘汰先看最直觉的暴力思路枚举所有子串的起点i和终点j然后写一个isPalindrome(s, i, j)去逐个字符比对。枚举子串本身是 O(n²)每个子串判断回文最坏又是 O(n)整体 O(n³)。n1000时就是十亿次字符比较在LeetCode的用例规模下基本必挂。我在初学阶段真写过这种代码当时还觉得思路挺清晰直到提交后看到超时红色大字才意识到问题。暴力的核心浪费在于判断s[i..j]是否回文时完全没有复用s[i1..j-1]的判断结果。而回文有一个天然的性质——一个子串如果是回文去掉首尾后依然回文。这个性质就是所有优化方案的出发点。所以后续的每一种解法本质上都在做同一件事想办法利用回文的对称性和子结构把重复的比较结果缓存或跳过。理解了这一点再看中心扩展、动态规划、马拉车就不会觉得它们是三个孤立算法而是同一个问题的三种不同优化视角。2. 中心扩展法我最推荐的面试首选写法2.1 核心思路与两种扩展形态中心扩展法的想法非常朴素回文串是关于中心对称的那我只要枚举每一个可能的“中心点”然后向左右两边同时扩展直到两边字符不再相等就能得到以该中心为对称轴的最长回文子串。这里有一个关键细节中心点有两种形态。奇数长度的回文中心是某一个具体字符比如aba的中心是b偶数长度的回文中心是两个字符之间的“空隙”比如abba的中心在b和b之间。所以枚举中心的时候必须同时考虑这两种情况分别调用同一套扩展逻辑再取较大值。为什么这个方法值得作为首选因为它空间复杂度是 O(1)不需要额外开二维数组实现逻辑也足够简单面试现场不容易写崩。时间复杂度 O(n²)对大多数面试场景完全够用。LeetCode原题的数据规模下中心扩展法也能稳定通过不像暴力法会超时。我实际写题时的心得是把“计算以某个中心开始的最长回文长度”抽成一个独立函数接收左指针和右指针作为起始位置内部用 while 循环扩展。这样主逻辑就非常干净奇数偶数两种中心点调用两遍即可也不容易漏边界条件。2.2 完整代码实现与参数说明class Solution: def longestPalindrome(self, s: str) - str: if not s or len(s) 1: return start 0 max_len 1 def expand_around_center(left: int, right: int) - int: # 向左右两边扩展返回扩展后的回文长度 while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 # 循环结束时 left 和 right 已经越界或指向不相等字符 return right - left - 1 for i in range(len(s)): # 奇数长度回文中心是 s[i] len1 expand_around_center(i, i) # 偶数长度回文中心在 s[i] 和 s[i1] 之间 len2 expand_around_center(i, i 1) cur_len max(len1, len2) if cur_len max_len: max_len cur_len # 根据回文长度反推起始位置注意偶数长度的偏移 start i - (cur_len - 1) // 2 return s[start:start max_len]这里有三个容易出错的位置需要重点说明。第一expand_around_center返回的是right - left - 1因为循环退出前最后一次left - 1; right 1已经把指针推到了不合法位置真正的回文区间是[left1, right-1]长度就是right-left-1。第二计算start时用i - (cur_len - 1) // 2这里加不加cur_len - 1很关键建议自己拿cbbd跑一遍体会偶数场景。第三初始max_len设为 1因为单字符本身一定回文字符串非空时答案长度至少是 1。我还建议在主函数开头先处理s为空的特殊情况直接返回空字符串。虽然LeetCode的用例不一定有空串但代码的健壮性是面试考核的一部分细节分不能丢。2.3 为什么中心扩展比动态规划更适合现场写我自己在面试时基本首选中心扩展原因很现实动态规划虽然思路也清晰但要维护二维数组dp[i][j]当场写的时候很容易在遍历顺序上翻车马拉车算法代码更短但原理绕讲不清楚反而减分。中心扩展是一个“思路简单、代码好写、复杂度达标”的均衡解面试官问复杂度也能对答如流。对比一下两者的实际代码体积中心扩展大概 20 行内搞定动态规划要额外初始化二维数组并处理斜向依赖马拉车则需要预处理字符串和计算p数组。从记忆负担来讲中心扩展是最轻的。如果你面试时间紧张我建议先把中心扩展练到闭眼能写、每一个细节都能解释清楚再考虑进阶方案。3. 动态规划最严谨的递推思路3.1 状态定义与状态转移方程动态规划的解法和中心扩展在思路上完全不一样它是从“子结构”入手的。定义dp[i][j]表示子串s[i..j]包含两端是否为回文。那么可以写出递推关系dp[i][j] (s[i] s[j]) and (j - i 3 or dp[i1][j-1])这个方程怎么理解如果s[i] ! s[j]那s[i..j]一定不是回文因为首尾都不等。如果首尾相等那s[i..j]是不是回文就取决于去掉首尾后的s[i1..j-1]是不是回文。这里有个特例当区间长度小于等于 3 时只要首尾相等中间只剩 0 个或 1 个字符必定回文所以不需要再看dp[i1][j-1]。这个“长度小于 3 直接为真”的细节其实就是j - i 3这一项存在的原因。很多人写动态规划时漏掉这个条件导致数组访问越界或结果错误。边界情况单独用if处理也是一种方式但把条件直接写进转移方程更优雅也能少写分行代码。3.2 遍历顺序是最大的坑动态规划版本的代码我写了不止一次每次栽跟头都栽在遍历顺序上。因为dp[i][j]依赖dp[i1][j-1]也就是说长区间的答案依赖更短的区间。如果按照i从 0 到 n、j从 i 到 n 的顺序去填表你会发现计算dp[0][4]时dp[1][3]可能还没算出来结果全是错误的。正确做法是按子串长度从小到大遍历。先算长度为 1 和 2 的所有子串再算长度为 3 的依次往上。对应代码就是外层循环枚举长度L内层循环枚举起始位置i终点j i L - 1。初始化时dp[i][i] True单个字符长度为 2 的子串直接判断s[i] s[i1]。我在实际刷题中犯过一个很蠢的错误先初始化dp[i][i] True也处理了长度 2 的情况但外层长度循环从 1 开始而不是从 2 开始导致重复计算和数组越界。后来养成了习惯——先列清楚长度为 1、2 的基例再从长度 3 开始递推逻辑就顺了。3.3 完整代码与空间优化class Solution: def longestPalindrome(self, s: str) - str: n len(s) if n 2: return s dp [[False] * n for _ in range(n)] start 0 max_len 1 # 长度为 1 的子串一定是回文 for i in range(n): dp[i][i] True # 按长度从小到大遍历 for L in range(2, n 1): for i in range(n - L 1): j i L - 1 if s[i] ! s[j]: dp[i][j] False else: if L 3: # 长度 2 或 3 时首尾相等即为回文 dp[i][j] True else: dp[i][j] dp[i 1][j - 1] if dp[i][j] and L max_len: start i max_len L return s[start:start max_len]动态规划的优点是思路严谨、状态定义清晰面试时讲递推方程会显得你基础扎实。缺点是空间复杂度 O(n²)当字符串长度上万时内存吃不消。不过 LeetCode 原题 n 最多 1000完全没问题。如果想要空间 O(n) 的降维版可以用一维数组滚动更新因为dp[i][j]只依赖dp[i1][j-1]本质上只依赖上一层的左下方位置。但注意压缩时遍历方向要按i从大到小否则会覆盖掉还没用到的旧值。我个人建议面试时先写二维版本简单直观不容易出错等面试官追问空间优化再提一维版本。4. 马拉车算法线性复杂度的进阶武器4.1 预处理技巧与对称性利用马拉车算法的目标很明确把时间复杂度压到 O(n)。它充分利用了回文的镜像对称性。具体做法是先对原字符串做预处理在每个字符之间以及首尾都插入一个特殊分隔符比如#。原字符串abc变成#a#b#c#这样做的好处是统一了奇偶长度回文所有回文在新串中都变成奇数长度中心必然落在某个字符或#上。然后定义一个数组p[i]表示以新串第i个位置为中心能扩展出的回文半径包含中心本身。比如#b#中p[2] 2。核心优化在于维护当前所有回文中右边界最靠右的一个记其中心为mid、右边界为right。当计算新的位置i时先利用mid的对称性找到i的镜像位置i_mirror 2 * mid - i。如果i right那p[i]至少可以取min(p[i_mirror], right - i)因为i的回文至少能覆盖到right以内与镜像位置对称的部分。直接看代码可能更清楚我写过一个注释比较详细的版本。4.2 马拉车标准实现class Solution: def longestPalindrome(self, s: str) - str: # 预处理插入分隔符 t # #.join(s) # n len(t) p [0] * n mid 0 right 0 max_radius 0 max_center 0 for i in range(n): if i right: # 利用对称性初始化 p[i] i_mirror 2 * mid - i p[i] min(p[i_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 # 更新最右边界 if i p[i] right: mid i right i p[i] if p[i] max_radius: max_radius p[i] max_center i # 还原原始字符串中的起始位置 # 原串回文长度 max_radius - 1 orig_len max_radius - 1 start_orig (max_center - max_radius 1) // 2 return s[start_orig:start_orig orig_len]这里的“继续扩展”一段和中心扩展法的逻辑类似但因为有了前面p[i]的初始值很多位置的比较次数被大幅压缩总体复杂度降到线性。关于还原部分新串中中心为max_center、半径为max_radius的回文对应原串起点是(max_center - max_radius 1) // 2原串回文长度是max_radius - 1。这个换算我第一次推的时候还花了点时间直接记结论再配合两个例子验证即可。马拉车虽然代码不长但在面试中属于加分项。我一般在面试官追问“能不能做到 O(n)”时才提它。值得注意的是马拉车对理解对称性和边界条件的要求较高如果你在现场不能把p[i]的初始值为什么是min(p[i_mirror], right - i)讲清楚建议不要主动往这个方向引以免被追问到露怯。4.3 三种解法怎么选我给你的选型建议是这样的如果面试时间紧、压力大直接上中心扩展稳扎稳打如果面试官明确要求用动态规划展示递推思维再写二维 DP如果 String 类题目你已经刷得很熟马拉车作为储备能让你在“复杂度还能不能再优化”的问题上游刃有余。我在实际工作中写业务代码几乎不会遇到需要马拉车的场景但刷题和面试是完全另一套评价体系。这道题三种解法全掌握相当于把字符串处理里最经典的对称性问题彻底吃透了后面遇到“最长回文子序列”“回文对”等变种题也能有个清晰的类比基础。5. 边界测试与高频错误排查实录5.1 必测的边界用例清单无论用哪种解法提交前我建议你把这组用例在本地跑一遍能覆盖绝大多数边界场景用例期望输出陷阱说明aa单字符最容易忽略但最简单aaaa偶数回文测试中心扩展的第二种形态aba无回文时返回单字符即可babadbab或aba多个答案都合法不要纠结cbbdbb标准偶数回文aaaaaaaa全部相同字符压力测试空串直接返回我自己刷题时习惯把这些用例写成函数调用的形式批量测试而不是手动一个一个看。写一个简单的断言列表跑一遍省心很多。尤其是aaaa这种用例能暴露中心扩展里start计算错误的问题。5.2 三个高频错误与修复方法第一个高频错误是中心扩展法的start位置算错。表现为输入cbbd时输出b而不是bb。问题基本都在start i - (cur_len - 1) // 2这条公式上。我建议复盘时用i1, cur_len2代入字符串cbbd中中心在b和b之间你会发现如果不减 1算出的起点会偏右一位切出来的子串就不是完整回文。第二个高频错误是动态规划遍历顺序写错。很多人按i从前往后、j从i往后去填表结果答案完全不对。只要记住一句口诀子串题意依赖短串长度从短到长遍历。外层循环一定是长度内层才是起点这个顺序反了整个表都是脏数据。第三个高频错误是马拉车里right - i与p[i_mirror]取最小值时理解不清。有些人直接写p[i] p[i_mirror]在镜像位置的回文超出当前右边界时就会越界或结果偏大。正确写法必须带上min约束因为超出right的部分还没被验证过不能直接镜像推断。5.3 面试中常见的追问方向面试官大概率会追问这三类问题。第一是“为什么中心扩展时间复杂度是 O(n²)”回答思路枚举中心 O(n)每次扩展最坏 O(n)两者相乘。强调最坏情况是全部字符相同的时候每次扩展都要走到边界。第二是“动态规划还能优化空间吗”提一维滚动数组但注意说明遍历方向要调整。第三是“马拉车为什么能做到 O(n)”解释right边界只增不减每个位置最多被扩展成功一次失败则立即停止所以总扩展次数是线性的。这些问题都不难但前提是你真的理解了你写的每一行代码。我在面试别人的时候经常发现能把中心扩展讲清楚的人很多但能把 DP 的遍历顺序和马拉车的min分支讲明白的人少一半。这差距就是准备的深度问题。6. 一点刷题实战体会这道题我刷过好几轮每次重刷都有新的理解。第一次学动态规划硬背代码过两天就忘了第二次认真推导状态转移方程总算明白了遍历顺序的来源第三次系统学习马拉车才真正理解“对称性复用”的精妙。所以如果你第一次看完没完全吃透非常正常这不是一道看一遍就能会的题。我的建议是先用中心扩展法把题过了然后隔一天再用动态规划重新写一遍不参考任何资料看看能不能自己推导出遍历顺序。最后再挑一个周末啃一下马拉车把p[i] min(p[i_mirror], right - i)这个关键算式亲手在纸上验证两个例子。三步走完这道题才算真正转化成你自己的能力。另外提醒一句LeetCode Hot 100 里回文相关的题不止这一道“回文子串”“最长回文子序列”都和它有关联。把第 5 题吃透后面遇到这些变种会轻松很多。