最长回文子串LeetCode第五题也是热门100题里被点频率最高的一道字符串题。不管是大厂面试还是周赛练手这题出现的概率都相当高。我见过不少刷题群的上岸经验帖把它列为“必会”原因很简单它考察的是最基础的字符串处理能力而它的两种主流解法和动态规划法各代表了两种典型的算法思维。中心扩展法代码短、空间O(1)动态规划法思想通用、适合延伸两个版本吃透之后再遇到“统计回文子串”“最长回文子序列”这类变体题基本就是套模板的事。这篇文章直接把中心扩展法和动态规划法都拆开讲包括代码每行的意图、为什么时间复杂度是O(n^2)、哪里有极其隐蔽的坑一次性讲透。1. 题目解析审题阶段最容易丢分1.1 回文子串的定义先明确什么是回文一个字符串正着读和倒着读完全一样比如“aba”“bb”“a”都是回文。而“回文子串”意味着这个回文必须是原字符串里连续的一段而不是随便挑几个字符组成的子序列。这个区别很关键因为子序列问题通常更难比如LeetCode第516题“最长回文子序列”那题的做法是区间DP讨论删除部分字符而第五题只要求连续的子串。官方给的例子是s babad输出需要是bab或者aba这两个都是正确的回文子串长度均为3。另一个例子s cbbd输出bb。注意一个细节如果存在多个答案返回任意一个即可所以不需要纠结到底选哪个最长子串。我自己刚开始刷这题时就犯过执念错误非要找到所有答案再选一个顺序靠前的白白浪费了时间。实际写代码时只需要找到任意一个最长回文子串并返回。1.2 输入边界条件LeetCode第5题给的s长度在1到1000之间其实不会出现空串但我建议还是把空串的情况写进代码里一方面让逻辑更完整另一方面面试官可能随手加一个极端测试用例考察你的边界意识。如果s长度为0直接返回空字符串如果长度为1单个字符自身就是回文直接返回s。这些判断虽然看起来简单但漏写会导致索引越界之类的问题。还有一个容易踩的坑题目要求返回子串本身而不是返回子串长度。我见过有同学写了完全正确的长度计算逻辑最后return max_len结果编译通过但答案全错。LeetCode的判题系统对返回值类型有明确要求这个点必须看仔细。1.3 和暴力法的差距最直观的解法是枚举所有子串然后一个个判断它们是不是回文。枚举所有子串需要O(n^2)个区间判断一个子串是否是回文需要O(n)的比较总复杂度就是O(n^3)。n1000的情况下已经是10^9次操作量级在LeetCode上几乎不可能通过。所以必须利用回文的对称性来优化。回文一个很关键的性质是如果一个回文串去掉首尾两个字符之后中间部分也一定是回文。比如“abcba”去掉首尾的“a”“a”后得到“bcb”它依然对称。这个性质同时启发了两种解法中心扩展法从中间向外扩动态规划法从短区间向长区间递推。它们本质上都是利用这个性质避免重复判断。2. 中心扩展法把回文看成镜面反射2.1 核心思路回文串一定存在一个对称中心。长度为奇数的回文中心是一个字符比如“abcba”的中心是“c”长度为偶数的回文中心是两个相邻字符的中间位置比如“abba”的中心是“bb”之间的虚线。基于这个事实可以枚举所有的对称中心。一个长度为n的字符串奇数中心有n个因为每个字符都能作为中心偶数中心有n-1个因为每对相邻字符中间都能作为中心。所以总共有2n-1个中心。每个中心向左右两侧扩展只要左右字符相等就继续扩直到不相等或者越界停止这样就能找到以该中心为对称轴的最长回文子串。这其实很像从一面镜子的位置向两边看能看到多远的对称风景。每个中心扩展过程中由于左右指针是同步移动的自然就能保证得到的子串是回文完全不需要额外判断。2.2 关键代码实现中心扩展法最大的优点是代码精简。如果定义一个辅助函数来处理向两边扩展的逻辑主函数的循环就非常清爽。这里给出我最终采用的版本def longestPalindrome(s: str) - str: if not s: return if len(s) 1: return s n len(s) start 0 max_len 1 def expand(left: int, right: int): # 从中心向两侧扩展返回能形成回文的最长区间[left, right]闭区间 while left 0 and right n and s[left] s[right]: left - 1 right 1 # 循环结束后合理区间是 [left1, right-1] return left 1, right - 1 for i in range(n): # 奇数中心以i为中心 l1, r1 expand(i, i) # 偶数中心以i和i1中间为中心 if i 1 n: l2, r2 expand(i, i 1) else: l2, r2 0, -1 # 不存在的区间 if r1 - l1 1 max_len: max_len r1 - l1 1 start l1 if r2 - l2 1 max_len: max_len r2 - l2 1 start l2 return s[start:start max_len]这段代码有四个地方值得细说。第一expand函数计算出的left和right是闭区间。当while循环结束left指向第一个不匹配的位置right也指向第一个不匹配的位置真正的回文区间是left1到right-1。所以函数返回left1和right-1。有些版本喜欢在expand里直接返回长度我觉得返回闭区间更不容易算错起始下标。第二主循环里为什么要分别调用奇数和偶数中心。因为标记中心的方式不同奇数中心用单个字符位置表示偶数中心用相邻两个字符的下标对表示。而最终最长的回文可能是奇数长度也可能是偶数长度必须两方面都尝试。第三我这里手动判断了i 1 n避免在最后一个字符上执行偶数扩展时expand函数做无意义的计算。虽然跳过了也不会有致命影响但处理成“不可能的区间”更严谨代码的可读性也更好。如果不加这个判断expand(n-1, n)会返回(n, n-1)是一个右边界小于左边界的不合法区间这种负长度区间虽然不会被更新为最优解但写多了容易让自己产生疑惑。第四记录答案用的是start和max_len最后返回s[start:start max_len]。Python的切片右边界是开区间所以start加max_len是正确写法。不要写成start max_len 1或者start max_len - 1那都会导致最终结果长度错误。2.3 复杂度分析证明它不是暴力中心数量是2n-1而每次扩展最多扩展到边界所以最坏情况下每个中心需要O(n)次比较总时间复杂度O(n^2)。空间复杂度上除了输入输出本身只用到了常数空间即O(1)这是它相比动态规划版本最大的优势。有人可能会问有没有可能进一步优化其实中心扩展法的最优复杂度就是O(n^2)因为最坏情况比如字符串是“aaaaa...a”全相同字符时每一个中心几乎都要扩展到边界。不过这种全相同的情况正好也提示了为什么复杂度不会降级成O(n^3)在中心扩展过程中每个中心向两边的比较是线性完成的不会像暴力法那样反复判断同一个区间。实际跑LeetCode第5题时n1000的情况下中心扩展法的耗时一般在20到40毫秒左右完全在安全范围。需要注意的一点是有些同学写中心扩展法时会在扩展内部调用切片去比较比如每次判断s[l:r1] s[l:r1][::-1]那复杂度就退化得非常严重。字符串切片本身是O(len)的复制操作再加上反转判断又需要O(len)等于把中心扩展的核心优势丢掉了。一定要直接通过下标访问s[left]和s[right]来比较字符。2.4 为何悖论上是“最简单”的实现我接触过不少刚开始刷题的同学都觉得中心扩展法不如动态规划法“高级”但实际上它恰恰是面试里最推荐手写的方案。理由很简单代码短、边界少、空间O(1)。动态规划虽然思路清晰但要处理二维数组初始化、遍历顺序、base case稍不留神就会写挂。中心扩展法只要记住“奇中心对(i,i)偶中心对(i,i1)向两侧扩展直到字符不匹配”基本就是满分答案。如果面试官继续追问让你优化到O(n)那就要拿出Manacher算法了不过那属于进阶内容这里先不展开。至少在我面试过的人里能把中心扩展法说得清楚、写得利落的已经超过了大部分候选人。3. 动态规划法区间上的状态转移3.1 为什么可以用区间DP题目要求最长回文子串本质上是判断某一段连续区间是不是回文。区间DP天然适合这类问题因为一个区间是否回文可以由它的子区间推导出来。设dp[i][j]表示字符串s从下标i到下标j这一段的子串是否为回文取值True或False。当i等于j时单个字符当然是回文。当i和j相邻时只要s[i]等于s[j]两个字符就构成回文。当j - i 2时s[i:j1]是回文的条件有两个s[i]等于s[j]并且内部区间s[i1:j]也要是回文。这正是之前提到的“删掉首尾仍为回文”的性质。这个状态转移方程很少发生歧义真正麻烦的是遍历顺序。因为dp[i][j]依赖于dp[i1][j-1]而dp[i1][j-1]在表格中的位置是dp[i][j]的“左下角”。如果按普通二维数组从上到下、从左到右的顺序遍历外层i内层j计算dp[i][j]时dp[i1][j-1]还没有被计算出来结果就是False整个答案就会错。3.2 标准的状态转移代码正确的做法是按照子串长度从小到大递推先算所有长度为1的子串再算长度为2的子串然后是长度为3、4……这样在计算长区间时内部短区间都已经有了结果。我写了一个常见且争议较少的版本def longestPalindrome(s: str) - str: n len(s) if n 0: return dp [[False] * n for _ in range(n)] start 0 max_len 1 # 所有长度为1的子串都是回文 for i in range(n): dp[i][i] True # 按长度从2到n递推 for L in range(2, n 1): for i in range(n - L 1): j i L - 1 if s[i] s[j]: if L 2: dp[i][j] True else: dp[i][j] dp[i 1][j - 1] if dp[i][j] and L max_len: max_len L start i return s[start:start max_len]外层循环L表示当前枚举的子串长度内层循环i表示子串左端点右端点j通过i L - 1计算。当L为2时子串只有两个字符不存在“内部区间”所以直接根据s[i]s[j]判定当L大于2时才依赖dp[i1][j-1]。这个特判写清楚能避免之后很多无意义的调试。3.3 遍历顺序错误演示与修正我见过一个非常常见的错误版本也是我自己第一次写DP时踩过的坑。错误版本长这样# 错误写法注意这是错误示例 for i in range(n): for j in range(i 1, n): if s[i] s[j] and (j - i 2 or dp[i 1][j - 1]): dp[i][j] True问题在哪里呢当外层循环i从0开始跑时它会先更新所有j个状态比如dp[0][3]需要依赖dp[1][2]但dp[1][2]属于第1行而第1行的所有结果要等外层i1时才计算。所以此时dp[1][2]是初始值False导致dp[0][3]被错误判定为False。如果运气好某些依赖值因为初始化就是True可能碰巧正确但大多数情况都会算错。解决办法除了按长度递推也可以这样写外层循环枚举右端点j内层循环让左端点i从j-1递减到0。这样计算dp[i][j]时因为右边界是j-1的整列都已经算完了dp[i1][j-1]自然可用。两种方式都能跑但“按长度递推”和“按右端点递推”里前者最直观最能体现区间DP的思路面试时也最好解释。3.4 空间压缩从O(n^2)到O(n)动态规划二维数组的空间复杂度是O(n^2)在n1000时是100万布尔值勉强能接受。但如果面试官追问能不能把空间优化一下实际上可以压缩到O(n)。思路是基于按右端点递推的写法。设dp[j]表示以j为当前最右端点时从左端点i到j这一段是否回文但一维数组在枚举i的过程中要滚动更新。关键是当我们从大往小枚举i时dp数组中的状态需要及时更新。一个可行的版本def longestPalindrome(s: str) - str: n len(s) if n 0: return dp [False] * n start 0 max_len 1 for j in range(n): dp[j] True # 长度为1的子串 for i in range(j - 1, -1, -1): if s[i] s[j] and (j - i 1 or dp[i 1]): dp[i] True if j - i 1 max_len: max_len j - i 1 start i else: dp[i] False return s[start:start max_len]这里的核心是外层j是右端点内层i从近到远递减枚举。当计算区间[i, j]时dp[i1]恰好保存了上一轮右端点j-1时区间[i1, j-1]的结果。这个“上一轮”的状态在还没有被本轮覆盖前是有效的所以可以一维滚动。要注意的是如果当前s[i]不等于s[j]必须手动把dp[i]置为False否则下一轮更长的区间会错误地依赖这个残留的True。这个细节非常隐蔽初次写一维版本很容易被它坑到我就是调试了大半天才反应过来。虽然空间优化看起来更高端但在面试中如果能在5分钟内写出二维DP并解释清楚其实已经合格。空间优化作为加分项提一句就好没有必要写在白板上除非面试官明确追问。4. 实战对比两种方法到底如何选4.1 不同维度的选择标准维度中心扩展法动态规划法时间复杂度O(n^2)O(n^2)空间复杂度O(1)O(n^2)可优化为O(n)代码量短主函数加辅助函数约15行中等二维数组初始化加循环约25行边界处理奇偶中心分开处理需要特判长度为2的区间扩展学习意义善于处理单个中心对称问题是区间DP的基础模型可迁移到序列问题从工程角度讲如果只要求解“最长回文子串”这一道题中心扩展法绝对是首选。原因很简单时间复杂度同为O(n^2)但中心扩展法常数更小实际运行速度更快。LeetCode官方数据上中心扩展法通常比基础DP快一倍以上因为DP要处理整个二维表而中心扩展对很多不相等的相邻字符根本不会扩展太远。再从面试角度讲面试官通常更希望看到你对两种解法都有理解然后根据场景选择最优方案。如果你只会DP而不会中心扩展也不算大问题但如果你能主动指出“这题用中心扩展法可以做到O(1)空间DP空间是短板”这会是很好的加分表示。4.2 测试用例设计与验证写算法题时养成设计测试用例的好习惯比直接提交跑判题系统更高效。针对这题我常用的测试集如下输入s期望结果覆盖场景空串边界aa单字符aca 或 c无相邻相同字符的偶回文bbbb相邻双字符回文babadbab 或 aba多个等长答案题目允许任一cbbdbb偶数长度回文abcbaabcba奇数长度回文中心字符唯一aaaaaaaa全相同字符中心扩展最坏情况abccccddcc 或 dd短偶数回文我每次改完算法先用这组测试集跑一遍再提交LeetCode。要是直接在判题系统上反复试错被罚时体验会差很多。自己搭建的测试集能快速定位是索引问题还是状态转移问题。4.3 经验面试时写哪一种一个比较折中的建议让面试官看到你具备两种思路。你可以先说“这题常见做法有两种中心扩展法空间最优动态规划法思路更具拓展性我先把中心扩展法写出来”然后代码完成后如果时间充裕再口述DP的转移方程。这样既展示了代码能力又展示了理论基础。5. 常见问题与排查技巧实录5.1 中心扩展写歪了奇偶中心分不清很多同学在写中心扩展时只考虑“以某个字符为中心”的奇数情况结果遇到“cbbd”这种偶数回文就漏了。排查方法非常简单跑一下“bb”这个用例如果输出的是“b”或者“cbbd”里的某个单字符那一定是偶中心漏了。把expand(i, i1)补上就对了。还有一种情况是记录答案时用了不正确的区间换算导致输出少字符。我建议统一用“返回开区间边界”或“返回闭区间边界”的思路在expand函数里计算完就返回左右下标主函数里只比较长度并更新start/end。不要在主函数里根据中心下标和长度去反推左端点那个推导很容易出错尤其是偶数长度的时候。5.2 DP结果全是False或者结果永远是第一个字符这是典型的遍历顺序错误。如果你把二维DP写成了外层i、内层j的正序枚举那么绝大部分区间的依赖状态还没有被计算dp[i][j]全军覆没。排查时加几个print语句或者选一个简单的用例“aba”手动走一遍流程就能看出来。另一个容易犯的错是初始化时只设置了dp[i][i] True忘了处理长度为2的情况然后外层循环的L从3开始。如果字符串只有一个形如“bb”的答案就会漏掉。我建议L直接从2到n循环在循环内用特判单独处理L2的情况逻辑上最统一。5.3 提交后显示内存超限在LeetCode第5题里内存超限相对少见因为n最大1000二维布尔数组大概1MB多一点。但如果你用的是Python且dp数组存的是1和0的整数而不是布尔值内存会翻好几倍。用[[False] * n for _ in range(n)]的写法就够了不要用[[0] * n] * n后者不仅内存没省还会因为共享引用导致赋值时所有行同时被修改。如果你非常在意内存直接用中心扩展法空间O(1)这个问题不存在。5.4 超过时间限制的排查如果代码是O(n^3)的暴力法n1000肯定超时。最直接的改进方法是替换成中心扩展或者DP别再试图优化暴力的常数。如果已经是O(n^2)的方法却仍然超时大概率是语言层面的性能问题比如在扩展循环里频繁切片、频繁拼接字符串、用字符串反转比较等。改成下标访问字符就能解决。LeetCode官方对这题的Python时间限制其实比较宽松中心扩展法和DP都能轻松通过。真遇到超时先检查自己的循环内有没有隐藏的O(n)操作。6. 延伸思考怎么把这题的收获用到其他题6.1 回文家族的题型串讲看完这题下一步最值得刷的是LeetCode第647题“回文子串”它要求统计所有回文子串的数量。中心扩展法直接就能改造每扩展到一个合法的回文区间计数加1复杂度同样是O(n^2)。第516题“最长回文子序列”则需要用到区间DP但不能直接照搬第五题的方程因为子序列允许跳过字符。第9题“回文数”则可以用反转后半部分数字的方法和字符串关系就不大了。如果把“中心扩展”的思想抽象一下很多字符串匹配和对称类题目都能受益。比如判断回文链表可以用快慢指针找到中点然后反转后半段这本质上也是一种“中心”思想。6.2 从这道题看LeetCode周赛和热门题的关系我在刷LeetCode周赛题目时多次遇到这类基于区间状态设计的变体题。周赛430里有个“统计回文子序列”相关的题目核心思路就是在区间DP的基础上加一层组合计数本质上就是对dp[i][j]做滚雪球式的扩展。如果你连第五题的DP都不能熟练掌握那个题目做起来会很痛苦。反过来把这道题练透之后基本计算器LeetCode第224题那种“表达式解析栈状态管理”的题反而会让你觉得根本不是一个套路正好借它来换换脑子避免陷入“只会DP不会其他”的僵局。LeetCode热门100题里最长回文子串属于那种“看着不难写对不易”的代表。很多人能背出中心扩展法的模板但一问转移方程为什么按长度枚举就卡壳。这也是为什么我总鼓励刷题之余适当看看题解区尤其看那些标注“从暴力到最优”的题解能帮你理解一个优化是怎么一步步被逼出来的。6.3 一点Beyond这题的建议如果你刷到LeetCode 875“爱吃香蕉的狒狒”或者这类二分答案的题会发现它们和回文题毫无关系但同样考察你能否把问题抽象成“单调性判定”。回文题考的是“对称性”二分题考的是“单调性”栈题考的是“延迟处理”树题考的是“递归分治”。把这些不同维度的模型都分类吃透再遇到新题时就能更快地定位到对应的套路。最后分享一个实操小技巧我看题解时注意到很多人会把“中心扩展法”的两个中心调用合起来处理用一个小技巧减少代码量for i in range(2 * n - 1): left i // 2 right (i 1) // 2 # 如果i是偶数left right即为奇数中心 # 如果i是奇数right left 1即为偶数中心这个技巧把2n-1个中心统一成一个循环代码看起来很精妙但可读性略差我一般不推荐在白板上写这种“聪明码”。面试的时候把奇偶两种情况分开写反而是更稳妥的。原因很简单人都会失误代码越简洁清晰边界越不容易出错而那种合并写法的确能用但万一面试官盯着问你“i为奇数时left和right分别是什么”很容易把自己绕晕。最后再啰嗦一句不管用哪种解法写完一定要自己手动跑一遍“babad”和“cbbd”这两个官方用例再跑一遍“aaaa”和“abcba”。这几个用例能覆盖绝大多数边界错误。等你把这题稳稳拿下后面再遇到“回文子串”“最长回文子序列”“回文链表”等等变体题你会发现它们都只是在这篇内容的基础上做了加减乘除而已。