聊到算法面试必刷清单最长回文子串LeetCode 5几乎是一定会出现的名字。这道题我当候选人时被面过不下十次后来自己做算法面试官也经常拿它当热身题。它之所以被各个大厂反复使用不是因为解法有多难背而是因为一道题就能考察到两种不同的思维路径一种是区间动态规划一种是线性复杂度的马拉车算法中间还夹着一个大家都能想到但细节极多的中心扩展。这篇文章我会把暴力、动态规划、中心扩展、Manacher 四种思路完整拆开附带可以直接背下来的代码以及面试时怎么一步步和面试官沟通把复杂度从 O(n³) 一路聊到 O(n)。1. 一道题刷出四层境界最长回文子串到底在考什么1.1 题目定义与基础概念题目描述很简单给定一个字符串s找到s中最长的回文子串。回文串就是正着读和反着读一样的字符串比如aba、racecar、abba。注意是子串也就是必须连续的一段不能像子序列那样跳着取。所以babad的最长回文子串是bab或者aba两者长度都是 3题目说返回任意一个都可以cbbd的最长回文子串就是bb。这道题在 LeetCode 上是中等难度但实际面试里的考察深度远超中等这两个字。原因在于它解法梯度非常清晰先是一个三层循环的暴力解让大家确认题目理解然后可以升级到动态规划或中心扩展的 O(n²) 解法最后还能延伸到 O(n) 的 Manacher 算法。每一层都需要不同的思维工具从枚举、递推到对称性优化恰好覆盖了算法面试最常问的几类能力。1.2 四种解法对应面试官的四种期待我面过不少候选人观察到一个规律大部分人在 10 分钟内能写出中心扩展法这是合格线能写出动态规划并解释清楚填表顺序的说明区间 DP 基本功扎实能主动提出 Manacher 或者在被追问后把线性算法讲明白的基本就是加分项了。很少有人会先写暴力解但真有人写的话我反而会好感度上升因为他展现了先确认问题再逐步优化的工程习惯。你需要知道的是面试官不是期待你一上来就甩出 Manacher而是看你能不能沿着暴力→优化→再优化的路径走下来。接下来我把每层境界都拆开讲包括代码和推导过程这样不管面试官问到哪一层你都有完整的答案。1.3 为什么说这道题是最典型的面试题典型之处在于它的边界条件特别容易出错。空串返回什么单个字符算不算回文字符串长度是偶数还是奇数这些细节会直接影响代码里的循环范围和返回值。另一层典型体现在复杂度选择的权衡O(n²) 时间 O(1) 空间的中心扩展在绝大多数场景下已经够用但一旦面试官追问如果字符串长度是百万级别呢你就得有 O(n) 的备用方案。我自己的经验是刷这道题时不要只背代码要把四种解法当成四个独立的小项目来理解。理解了每种解法背后的为什么面试时你才能做到游刃有余。下面给出四种解法的复杂度对比方便你有个整体印象解法时间复杂度空间复杂度面试推荐度暴力枚举O(n³)O(1)提思路即可不推荐写动态规划O(n²)O(n²)可写考察区间 DP中心扩展O(n²)O(1)强烈推荐最稳妥ManacherO(n)O(n)加分项用于深入追问2. 暴力解不是白写的枚举所有子串时能看出哪些门道2.1 最直接的思路枚举所有子串再逐个判断暴力解法分两步第一步枚举所有子串第二步对每个子串判断它是否回文。枚举子串需要确定起点和终点双层循环是 O(n²) 个子串每个子串判断回文用双指针从两端向中间扫描又是 O(n)。三层嵌套下来就是 O(n³)。代码大概长这样def longestPalindrome_bruteforce(s: str) - str: n len(s) if n 2: return s max_len 1 start 0 # 枚举所有起点和终点 for i in range(n): for j in range(i, n): # 判断 s[i:j1] 是否是回文 l, r i, j ok True while l r: if s[l] ! s[r]: ok False break l 1 r - 1 if ok and j - i 1 max_len: max_len j - i 1 start i return s[start:start max_len]这段代码在面试里建议不要真的从头写到尾除非面试官明确让你给出最朴素版本。你只需要口头描述一下我可以枚举所有子串然后逐个用双指针验证然后紧接着指出复杂度是 O(n³)面试官通常就会让你继续优化。能主动分析复杂度比闷头把代码写完更重要。2.2 剪枝思路把枚举顺序倒过来暴力解法有一个很容易想到的优化既然要找最长的那就从最长的子串开始枚举找到第一个回文就直接返回。这种从长到短 提前终止的策略能把平均运行时间缩短很多虽然最坏复杂度还是 O(n³)但实际跑起来快不少。还有一种优化是在判断回文之前先做一次长度剪枝如果当前枚举的子串长度小于已经找到的最长回文长度直接跳过没必要再判断。这个剪枝在随机字符串上效果尤其明显。不过我必须坦白说这类剪枝属于工程上的微调面试中谈一谈可以体现「你考虑过常数优化」但不要指望它能改变算法等级。2.3 暴力的真正价值当测试基准和兜底方案很多人觉得暴力解一无是处我不同意。暴力解的代码逻辑最简单几乎不可能因为边界条件写错所以它天然适合做基准实现。我在自己刷题时有个习惯先用暴力解跑通再用中心扩展或者 Manacher 去验证随机输入的结果是否一致。你会发现高级算法在边界处理上一旦写错跑几个大用例很难看出来但和暴力结果一对比问题立刻暴露。面试里如果你时间充裕也可以采取类似策略先和面试官说明暴力思路然后在实现更优解法时用简单例子手动推演验证。这种「先能跑通再谈优化」的工程思维其实比算法本身更容易打动面试官。3. 动态规划版本回文子串的区间递推3.1 dp 数组的定义与状态转移推导动态规划的核心是把大问题拆成小问题。对于一个子串s[i..j]闭区间它是否为回文串取决于两个条件s[i]是否等于s[j]以及去掉两端后的s[i1..j-1]是否为回文串。用数学表达就是dp[i][j]表示s[i..j]是否为回文字符串布尔值当s[i] s[j]时dp[i][j] dp[i1][j-1]当s[i] ! s[j]时dp[i][j] false这里需要单独处理基线条件长度为 1 的子串一定是回文所以dp[i][i] true长度为 2 的子串只要s[i] s[i1]就是回文所以dp[i][i1] (s[i] s[i1])。这两个条件可以合并到状态转移里写成dp[i][j] (s[i] s[j]) and (j - i 3 or dp[i1][j-1])这里的j - i 3意思是长度为 1 或 2 的子串因为闭区间长度是 j-i1只要两端字符相等就直接是回文不需要看中间部分。用这个写法可以少写两个显式的初始化分支代码更简洁。3.2 填表顺序为什么必须先短后长这部分是动态规划最容易出错的地方。dp[i][j]依赖的是dp[i1][j-1]也就是长度更短的子串。如果按起点 i 从前往后遍历、终点 j 也从前往后遍历那么计算dp[i][j]时dp[i1][j-1]可能还没被计算出来。正确做法是先枚举子串长度再枚举起点。长度从 2 开始逐步增加到 n这样才能保证计算长区间时所有短区间的结果都已经就绪。曲线救国的方式也可以让 i 从大到小遍历、j 从小到大遍历同样能保证dp[i1][j-1]先于dp[i][j]被计算。不过最直观、最不容易出错的还是按长度枚举。3.3 完整代码与空间优化方向下面用 Python 实现一遍尤其注意start和max_len的更新逻辑def longestPalindrome_dp(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 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: max_len length start i return s[start:start max_len]二维数组的空间复杂度是 O(n²)。如果面试官追问能不能压缩空间可以提一句其实只需要保留上一轮长度的状态用一个一维数组滚动更新就能把空间降到 O(n)。具体做法是从右往左更新一维数组避免旧值被覆盖。不过说实话在面试中写二维版本是更安全的选择空间优化口头说明即可真要写的话反而容易因为顺序问题翻车。面试中谈到动态规划还有一件事容易被追问为什么dp[i][j]的回文长度等于j-i1因为dp数组存的就是布尔状态最长回文长度只跟i、j的差值有关。这个想清楚后面的中心扩展法其实本质上就是另一种省空间的 DP 实现。4. 中心扩展法面试官眼里最稳的 O(n²) 解法4.1 回文的对称性才是核心洞察动态规划虽然思路清晰但二维数组的空间消耗并不理想。中心扩展法的出发点完全不同回文串天然是轴对称的所以每个回文串都有一个对称中心从这个中心向两侧扩展只要两侧字符相同就能继续构成回文。这个洞察带来的算法非常直观遍历字符串中的每一个位置把它当作回文中心然后向左右两侧扩展记录能扩展到的最大长度。关键点在于回文的中心有两种情况奇数长度回文的中心是一个字符比如aba的中心是b偶数长度回文的中心是字符之间的空隙比如abba的中心在中间两个b之间。所以每个位置不仅要当作单独字符中心试一次还要当作空隙中心试一次。4.2 为什么是 2n-1 个中心一个长度为 n 的字符串有 n 个字符位置可以作为奇数回文的中心有 n-1 个字符之间的空隙可以作为偶数回文的中心合计 2n-1 个中心。对每个中心向两边扩展的代价最坏是 O(n)所以总时间复杂度是 O(2n-1) × O(n) O(n²)。空间上只需要几个变量是 O(1)。我在面试中经常让候选人写这个解法因为它的代码量很短但对中心这个概念的理解要求很高。如果你能清晰地说出 2n-1 的来源并且分别处理奇偶两种情况那基本就过关了。4.3 完整代码与边界处理中心扩展的代码我建议直接背下来它足够短而且不容易出错def longestPalindrome_expand(s: str) - str: if not s or len(s) 1: return start 0 end 0 for i in range(len(s)): # 奇数长度回文中心为 i len1 expand(s, i, i) # 偶数长度回文中心为 i 和 i1 之间的空隙 len2 expand(s, i, i 1) cur_len max(len1, len2) if cur_len end - start 1: start i - (cur_len - 1) // 2 end i cur_len // 2 return s[start:end 1] def expand(s: str, left: int, right: int) - int: while left 0 and right len(s) and s[left] s[right]: left - 1 right 1 # 循环结束后left 和 right 已经越过了回文边界 # 回文长度为 right - left - 1 return right - left - 1这里容易踩的小坑是坐标换算。当算出回文长度cur_len后新的起点是i - (cur_len - 1) // 2终点是i cur_len // 2。这个式子对奇偶两种情况都成立你可以拿cbbd里的bb手推一遍中心是 i1 和 i2 之间expand返回 2start 1 - 0 1end 1 1 2结果正好是s[1:3] bb。4.4 DP 和中心扩展怎么选时间复杂度上两者都是 O(n²)但中心扩展的空间优势太明显了DP 需要 O(n²) 的布尔矩阵中心扩展只需要 O(1)。所以在面试场景下我的建议是优先写中心扩展它代码更短、空间更少、逻辑也更直观。动态规划的价值在于体现你掌握区间 DP 这种更通用的工具而且有些题目比如回文子序列必须依靠 DP 思路。所以两道题都该会但针对这道题本身中心扩展是对大多数候选人来说性价比最高的答案。5. Manacher 算法从 O(n²) 到 O(n) 的关键三步5.1 预处理用 # 和哨兵统一奇偶回文Manacher 算法是这一题的正统 O(n) 解法它的优化思路是利用已经算出来的回文信息避免重复扩展。新手第一次看 Manacher 基本都会被绕晕我按三个步骤拆开讲每一步都有对应的物理意义。第一步预处理字符串。把原始字符串的每个字符之间插入一个特殊字符#并且在开头和结尾再加两个哨兵字符比如^和$。例如abba变成^#a#b#b#a#$。#的作用是把偶数长度回文的空隙中心变成显式的字符中心这样一来不管原来的回文是奇数长度还是偶数长度在新字符串里都统一以某个字符为中心。哨兵的作用是让扩展循环到达边界时必然失配从而不需要做越界判断。第二步定义回文半径数组p[i]。它的语义是以新字符串的第 i 个字符为中心能向两侧扩展的最大步数。也就是说t[i-p[i] .. ip[i]]这一段一定是回文。特别地原始字符串中的最长回文子串长度就恰好等于max(p)。5.2 p 数组的镜像复用逻辑第三步是整个算法的核心维护两个变量center和right分别表示当前已知最右回文串的中心和右边界。当你需要计算某个位置 i 的p[i]时如果 i 在right的左侧说明 i 落在一个已知回文范围内。利用回文的对称性i 关于center的镜像位置是mirror 2 * center - i而镜像位置的回文半径p[mirror]大概率已经被算过了。这时候分两种情况如果镜像的回文范围完全落在已知回文串内那么p[i]至少等于p[mirror]如果镜像的回文范围超出了已知回文串的左边界那么p[i]至少等于right - i再往外就要暴力扩展了。综合起来就是if i right: p[i] min(p[mirror], right - i)这个min是 Manacher 的精髓它保证了你不会去扩展一个已经被确认过的范围只在必要时才暴力扩展。5.3 均摊 O(n) 的原因为什么总复杂度是 O(n)关键在于right这个右边界是单调递增的。每次暴力扩展成功一次right就会变大一点而right最多只能到数组末尾。换句话说虽然每个位置都可能触发扩展但整体扩展成功的次数被right的上限限制住了。暴力扩展的总次数是 O(n)再加上每个位置 O(1) 地计算p[i]初始值总复杂度就是 O(n)。这个均摊分析在面试时值得详细讲给面试官听能体现出你真的理解而不是背模板。5.4 完整代码与容易写错的三处细节我给出一个可以直接跑的 Python 实现def longestPalindrome_manacher(s: str) - str: if not s: return # 预处理插入 # 并加哨兵 t ^# #.join(s) #$ n len(t) p [0] * n center 0 right 0 max_len 0 max_center 0 # 跳过最左和最右的哨兵 for i in range(1, n - 1): if i right: mirror 2 * center - i p[i] min(p[mirror], right - i) # 暴力扩展利用哨兵避免了越界判断 while t[i p[i] 1] t[i - p[i] - 1]: p[i] 1 # 更新 center 和 right 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]这里有三处经常写错的地方我特别标一下先更新center和right再更新答案。因为right可能因为当前 i 的扩展而变大如果不先更新后面的位置就会用到一个过期的右边界。p[i]的初始值不是固定为 0而是min(p[mirror], right - i)这是算法能够跳过重复比较的关键。还原起点时是start (max_center - max_len) // 2不是max_center - max_len因为我们要把新字符串的下标映射回原始字符串的下标。5.5 一个额外收获回文子串计数Manacher 的p[i]还有一个作用直接数出所有回文子串的数量。以每个中心为轴半径从 1 到p[i]都可以构成一个回文所以把所有的p[i]加起来就是整个字符串中回文子串的总数。LeetCode 647 就是这道题。在面试中如果你能主动提到这一点面试官基本可以确认你真正掌握了 Manacher 而不是背了个模板。6. 面试实战从确认题意到被追问的完整话术6.1 动笔之前先和面试官对清楚这几件事我在面试中观察到能在写代码前主动沟通边界的候选人往往比直接上手写代码的更有好感。针对这道题动笔前至少要确认四件事第一输入字符串可能为空吗如果为空应该返回空串还是 null第二单个字符算回文吗按照通常定义单个字符天然是回文但最好和面试官确认。第三输入字符串包含哪些字符如果只有小写字母Manacher 的哨兵选^和$就很安全如果有任意 ASCII 或 Unicode需要考虑哨兵冲突或者改用边界判断。第四如果存在多个同样长度的最长回文子串返回任意一个即可吗LeetCode 原题说任意一个但还是确认一下更稳妥。这些问题不是走过场。有一次面试中候选人对空串和单字符做了显式处理后来代码在边界上几乎没有返工让我印象很深。6.2 测试用例与边界清单代码写完之后不要急着交差主动跑几个用例是加分项。我习惯的验证用例是空串返回单字符a返回a偶数长度回文cbbd返回bb奇数长度回文babad返回bab或aba全相同字符aaaa返回aaaa陷阱用例abacdfgdcaba这里abacdfgdcaba本身不是回文但aba和aba是容易让人误以为整个串是回文正好检验枚举逻辑两个互相重叠的中间有个bananasanana是最长回文手动推演两三个用例就够了重点是要把 push 到有回文中心但边界不对的例子比如aaabaaaa这种能暴露出你在更新start和end时的坐标错误。6.3 我踩过的坑和候选人常犯的错误第一坑中心扩展法里只处理了expand(s, i, i)而漏掉expand(s, i, i1)。这个词面看很简单但在紧张的面试环境中很容易漏漏掉之后所有偶数长度回文都会被跳过。第二坑动态规划填表顺序错误。这个一错那就是整体逻辑全崩因为dp[i1][j-1]还没算出来。第三坑Manacher 里p[i]初始值设成 0然后无条件扩展这样虽然结果不错但复杂度退回 O(n²)完全失去意义。第四坑坐标换算时把闭区间和半开区间搞混substring(start, end)和substring(start, end 1)差一个字符结果就是最长回文总是少了头或尾。我自己的教训是所有的坐标边界问题都要用长度为奇数和偶数的两个小例子去手动验证一遍。aba奇数中心和abba偶数中心是所有这类题目逃不掉的黄金测试对。手动推演一次比事后 debug 快得多。6.4 如果只剩 15 分钟就写中心扩展最后说点实战策略。面试中你的时间分配大约是5 分钟聊思路和边界10 到 15 分钟写代码最后 5 分钟测试验证。如果时间不够直接写中心扩展法它的代码量最小逻辑最容易自洽出 bug 的概率也最低。如果时间充裕且面试官明确对更优复杂度感兴趣可以上 Manacher但前提是你真的理解了right单调性的证明否则面试官一追问为什么是 O(n)就会露馅。顺着这个话题多说一句算法面试其实不只是考你会不会这道题更多是考你在有限时间内能不能给出一个正确、可解释、可验证的完整方案。最长回文子串恰好把所有经典要素都凑齐了所以把它刷透性价比真的很高。我至今写这道题时还是会先从中心扩展开始跑通再考虑要不要换 Manacher这个习惯帮我在多次面试里避免了低级失误也希望对你有效。