作为一个在 Java 后端圈子里摸爬滚打多年的老程序员我刷 LeetCode 算是把“最经典的一百题”翻来覆去研究过好几轮了。如果非要在这堆题里挑一道“面试中被问烂了、但每次都能刷掉一批人”的题目最长回文子串绝对排得上号。这道题在 LeetCode 上是第 5 题属于 TOP 面试题里的常青树不管是校招还是社招不管是面大厂还是面中小厂它出现的频率都高得吓人。今天我就以 Java 实现为主线把这道题的几种经典解法、我自己的调试经历、还有面试时容易被追问的细节全部扒开揉碎讲清楚。先说下这题到底是干嘛的给定一个字符串要求返回其中最长的回文子串。回文串就是正着读和倒着读都一样的那种比如babad里的bab和aba都满足条件返回任意一个都算对。这个“任意一个”其实是个伏笔很多解法都是围绕“找最长”来设计的你只要长度对、内容合法返回哪个都行。这题看着简单真要写出一个高效又正确的解法你会发现里面藏着不少门道动态规划、中心扩展、马拉车算法Manacher每一层都代表了对字符串问题理解的深度。我写这篇文章的初衷就是把我踩过的坑和总结出来的模板直接给你让你不光能 AC 这道题还能在面试时把思路讲得清清楚楚。1. 内容整体设计与思路拆解1.1 为什么这道题在面试中如此高频字符串相关问题在 Java 后端面试里属于“看起来简单、实际上最容易翻车”的板块。最长回文子串之所以被选中是因为它不是一个单纯的“背模板”题目它能用多种思路去解每一种思路背后都对应了一类算法思想暴力枚举对应了最朴素的逻辑思维中心扩展对应了“如何利用回文对称性”的观察力动态规划对应了“状态转移”的建模能力而马拉车算法则对应了“利用已有信息避免重复计算”的优化意识。面试官可以通过你选择的解法快速判断你的算法功底在哪个层级。我自己在面试别人时也很爱用这题来做考察。如果候选人上来就说“用动态规划”我会继续追问 dp 数组的含义、遍历顺序、为什么需要从下往上填如果候选人说“用中心扩展”我会追问奇偶长度怎么处理、最坏情况下的复杂度是多少如果候选人能提到马拉车那基本可以认定他的算法储备已经达到进阶水平。所以这篇文章不只是为了过题更是为了让你理解面试官每一个追问背后的动机。1.2 暴力解法为什么不可取很多人第一眼看到这题脑子里冒出来的解法就是枚举所有子串逐一判断是否为回文记录最长的那个。这个方法思路完全正确但时间复杂度是 O(n^3)——枚举所有子串需要 O(n^2)判断每个子串是否是回文还需要 O(n)。字符串稍微长一点就直接超时LeetCode 上可能连示例都过不了几个。我在初学阶段真的写过这种暴力代码还觉得“能跑就是好代码”结果一提交就被现实教育了。这道题的核心价值恰恰在于你能否在暴力思路上做出优化从“判断每一个子串”转变为“从一个中心向两边扩展”。这种转变不是凭空产生的而是基于回文串的天然对称性——回文串本身就是关于中心对称的结构判断一个字符串是否为回文本质上就是在验证对称性。既然我们要找的是最长的回文子串那为什么不直接以每个字符为中心去“生长”呢2. 中心扩展法——最容易理解和实现的解法2.1 核心思想与手动推演中心扩展法的思路其实一句话就能说清楚遍历字符串中的每一个位置把它当作回文串的中心然后向左右两边同时扩展直到左右字符不再相等为止此时记录下以该中心能形成的最长回文子串长度。由于回文串的长度可能是奇数也可能是偶数所以每个位置实际上要处理两种中心一个是以当前字符为中心的奇数长度回文一个是以当前字符和下一个字符之间的“空位”为中心的偶数长度回文。我刚开始学这个方法时总觉得“空位中心”很抽象后来自己拿cbbd手推了一遍就通了。这个字符串里最长的回文子串是bb它并不是以某个字符为中心的而是以两个b中间的缝隙为中心的。处理方式就是当扩展中心为i和i1时左右指针初始值分别为i和i 1比较这两个位置的字符如果相等就继续向外扩展这样就能正确覆盖偶数长度的情况。手动跑一个例子s babad以索引 1 的字符a为中心先看左右s[0]b和s[2]b相等继续扩展再看s[-1]已经越界停止。所以以索引 1 为中心的最长回文子串是bab长度为 3。再以索引 1 和索引 2 之间的空位为中心s[1]a和s[2]b不相等直接停止说明这里没有偶数长度的回文子串。整个过程就这么简单代码量也极小。2.2 Java 实现代码与边界细节我贴一下我平时最喜欢用的模板这个版本我在面试中手写过不下十次非常顺手public String longestPalindrome(String s) { if (s null || s.length() 1) { return ; } int start 0, end 0; for (int i 0; i s.length(); i) { int len1 expandAroundCenter(s, i, i); int len2 expandAroundCenter(s, i, i 1); int len Math.max(len1, len2); if (len end - start) { start i - (len - 1) / 2; end i len / 2; } } return s.substring(start, end 1); } private int expandAroundCenter(String s, int left, int right) { while (left 0 right s.length() s.charAt(left) s.charAt(right)) { left--; right; } return right - left - 1; }这里有两个细节值得注意。第一left和right在 while 循环结束时其实已经多向两边各走了一步所以回文串的长度是right - left - 1而不是right - left 1这个很容易写错。第二更新start和end时用start i - (len - 1) / 2和end i len / 2来还原回文串的起止位置这个公式对奇偶长度都适用不需要单独判断。这个解法的时间复杂度是 O(n^2)——每个位置最多向两边扩展 n 次空间复杂度是 O(1)不依赖额外数组在面试中属于“既能体现思路又不用担心空间爆炸”的稳妥选择。我实际测试下来对于 LeetCode 上这道题的测试数据这个方法的执行时间大概在 20ms 左右已经足够通过所有用例了。3. 动态规划解法——面试官最爱追问的版本3.1 状态定义与转移方程中心扩展法虽然好用但如果面试官想进一步考察你的动态规划功底他大概率会让你再想想“能不能用动态规划做”。动态规划解法的核心在于定义状态dp[i][j]表示字符串从下标i到下标j的这一段子串是否为回文串。有了这个定义状态转移方程就呼之欲出了dp[i][j] (s.charAt(i) s.charAt(j)) dp[i 1][j - 1]。翻译成人话就是如果当前两端的字符相等并且去掉两端后内部的子串也是回文那么当前这个子串就是回文。这个逻辑非常直觉但隐藏着一个关键细节——dp[i 1][j - 1]是较短子串的状态所以遍历顺序必须保证较短的子串先被计算出来。我之前在这里栽过跟头老老实实按照i从 0 到 n、j从 i 到 n 的顺序去填表结果发现计算dp[i][j]的时候dp[i 1][j - 1]根本还没算出来直接拿了默认值整个结果就全错了。正确的遍历方式有两种。第一种是按子串长度从短到长遍历先计算所有长度为 1 和长度为 2 的子串再逐步增加长度第二种是让i从字符串末尾往前走j从i往后走这样在计算dp[i][j]时dp[i 1][j - 1]一定已经被填充过。我个人更推荐第一种因为它的逻辑更直观也更方便后续初始化边界条件。3.2 Java 实现与复杂度分析按照长度遍历的写法如下public String longestPalindrome(String s) { int n s.length(); if (n 2) { return s; } boolean[][] dp new boolean[n][n]; int maxLen 1; int start 0; for (int i 0; i n; i) { dp[i][i] true; } for (int len 2; len n; len) { for (int i 0; i n - len; i) { int j i len - 1; if (s.charAt(i) ! s.charAt(j)) { dp[i][j] false; } else { if (j - i 3) { dp[i][j] true; } else { dp[i][j] dp[i 1][j - 1]; } } if (dp[i][j] len maxLen) { maxLen len; start i; } } } return s.substring(start, start maxLen); }这里有个容易让人迷糊的边界当j - i 3时为什么直接判定为 true因为长度为 1 或 2 的子串只要两端字符相等它一定是回文。比如aa两端都是a中间为空当然是回文再比如长度为 3 的aba两端相等且中间只有一个字符也一定是回文。这就省去了访问dp[i 1][j - 1]时可能出现的越界或依赖未初始化状态的问题。这个解法的时间复杂度是 O(n^2)空间复杂度也是 O(n^2)因为用了一个二维布尔数组。在 LeetCode 上跑起来大概 70ms 左右比中心扩展法慢一些但胜在状态转移清晰非常适合在面试中展示你对动态规划建模的熟练度。我个人经验是如果你时间充裕可以先讲中心扩展法作为最直接的思路再补充动态规划作为“从另一个角度思考”的方案这样整个回答的层次感会非常强。4. 马拉车算法Manacher——面试进阶的加分项4.1 预处理与核心数组的含义如果说中心扩展法和动态规划是面试的“标配”那马拉车算法就是实打实的“高配”。这个算法能把时间复杂度压缩到 O(n)是字符串处理领域一个非常精巧的优化。我第一次接触这个算法的时候被它的预处理步骤绕得晕头转向要在原始字符串的所有字符之间以及首尾插入一个特殊分隔符比如#这样无论是奇数长度还是偶数长度的回文串都能统一成奇数长度的形式。比如原始字符串aba预处理后变成#a#b#a#原始字符串bb预处理后变成#b#b#。这样做的好处是处理偶数长度回文时不再需要区分中心是字符还是缝隙——现在每个中心都对应一个实际存在的字符位置包括#。接着维护一个数组p[i]表示以预处理后字符串的第i个位置为中心的最长回文半径包含中心本身同时维护当前已知的最右回文边界maxRight和对应的中心center。4.2 核心优化逻辑与 Java 实现马拉车算法的高明之处在于它利用回文的对称性来避免重复扩展。想象一下如果你已经知道了一个很大的回文串它的中心是center右边界是maxRight。现在要计算这个回文串内部某个位置i的回文半径你可以利用i关于center的对称点mirror 2 * center - ip[mirror]已经算过了那么p[i]的初始值就可以直接取Math.min(p[mirror], maxRight - i)。这就相当于把之前算过的信息直接“搬”过来用不需要再从头扩展。Java 实现如下public String longestPalindrome(String s) { if (s null || s.length() 0) { return ; } StringBuilder sb new StringBuilder(#); for (char c : s.toCharArray()) { sb.append(c).append(#); } String t sb.toString(); int n t.length(); int[] p new int[n]; int center 0, maxRight 0; int maxLen 0, start 0; for (int i 0; i n; i) { if (i maxRight) { int mirror 2 * center - i; p[i] Math.min(p[mirror], maxRight - i); } int left i - (p[i] 1); int right i (p[i] 1); while (left 0 right n t.charAt(left) t.charAt(right)) { p[i]; left--; right; } if (i p[i] maxRight) { maxRight i p[i]; center i; } if (p[i] maxLen) { maxLen p[i]; start (i - maxLen) / 2; } } return s.substring(start, start maxLen); }这段代码里start (i - maxLen) / 2是一个典型的还原公式。因为原始字符串中的下标和预处理后字符串的下标存在对应关系预处理串下标i对应原始串下标i / 2而回文半径maxLen恰好等于原始串回文长度所以用(i - maxLen) / 2就能算出原始回文子串的起始位置。这个细节我第一次写的时候完全没搞懂后来在纸上画了好几遍才明白。马拉车算法虽然代码并不算长但每一个赋值背后都有严格的逻辑支撑面试时如果能把p[i]初始化和maxRight - i的作用讲清楚绝对能让面试官眼前一亮。我的建议是如果面试时间紧张或者你对这个算法还不够熟练可以只提一下“存在 O(n) 的马拉车算法”作为知识面的补充不要强行手写如果练得比较熟现场写出来就是妥妥的加分项。5. 常见问题与排查技巧实录5.1 面试高频追问与应对思路这道题在面试中几乎必然会有追问环节我梳理了几个被问频率最高的问题把应对策略一并写出来。第一个问题“中心扩展法和动态规划哪个更好”我的回答思路是从时间复杂度看两者都是 O(n^2)但中心扩展的空间复杂度是 O(1)动态规划需要 O(n^2) 的二维数组从理解难度看中心扩展更直白动态规划更偏建模。所以如果题目要求原地处理或内存受限优先中心扩展如果面试官重点考察动态规划思维那就选 DP。这题没有绝对正确答案关键是把你选择的原因说清楚。第二个问题“为什么动态规划中j - i 3可以直接返回 true”这个问题我在前面已经解释过面试时直接用长度为 1、2、3 的例子说明即可。还有一个变种问法是“如果字符串只有 1 个字符你的代码能正确处理吗”本质是在考察边界条件的覆盖情况。第三个问题“马拉车算法为什么能把复杂度降到 O(n)”关键在于每个位置最多被扩展一次因为maxRight是单调递增的一旦某个位置被计算过后续不会再从零开始扩展。这个性质我非常建议在纸上画一下理解了它才算真正掌握了马拉车。5.2 编写代码时最容易踩的坑第一个坑是我反复提到的二维 DP 遍历顺序问题。我见过太多人栽在这里明明状态转移方程写得完全正确结果因为遍历顺序导致结果错误。解决办法要么按长度从小到大遍历要么让i从大到小遍历二者选一即可。第二个坑是substring的边界问题。Java 的substring(start, end)是左闭右开区间即返回的字符串包含start但不包含end。所以在返回结果时如果你的结束下标是按“最后一个字符的位置”来算的一定要记得end 1。我在早期刷题时因为这个问题反复栽跟头后来索性统一用startlen来截取避免混淆。第三个坑是不处理空字符串和单字符的边界情况。如果输入是null或者空串很多解法会直接抛出空指针异常。我在写代码时习惯在最开头就加上if (s null || s.length() 0)的防御性判断这个习惯也延续到了日常开发中——健壮性优先永远不要相信入参。第四个坑是马拉车算法里忘记更新maxRight和center。这两个变量是整个算法“剪枝”的关键如果你算了p[i]却不更新maxRight那后续位置的对称性优化就全都失效了算法会退化成 O(n^2)。我调试这个 bug 的时候花了整整一个下午最后发现只是少了两行赋值语句那种懊恼的感觉到现在都记得。5.3 我的刷题与面试心得刷这道题我前后经历了好几个阶段。第一次接触时连暴力解法都写得磕磕绊绊第二次能写出中心扩展但不知道为什么right - left - 1第三次终于把动态规划的状态转移理顺了第四次才真正把马拉车算法的每一步推导搞懂。这个循序渐进的过程其实就是算法能力成长的真实写照——没有任何题是可以一蹴而就的反复锤炼带给你的不只是这道题的答案更是一种面对陌生问题时的分析方式。在面试实战中我建议大家采用“先讲思路、再写代码、最后验证”的节奏。先简明扼要说清楚你的解决方案是什么、复杂度是多少、为什么选择它然后动手写代码边写边注释关键逻辑写完后再用一个简单例子手动演算一遍展示代码的正确性。比如面试官让你做babad你可以在代码里跑完后口头输出bab或aba同时解释为什么这个结果是合理的。这样一套流程走下来哪怕代码有小瑕疵面试官也会对你的整体思维留下深刻印象。最后再分享一个我自己的小技巧平时练习时不要只满足于 AC试着把一道题的多解都写一遍然后横向对比它们的耗时和内存。LeetCode 会显示每个解法的执行时间和内存消耗用这个数据来验证你的复杂度分析是否准确是一个非常直观的学习方式。就拿这题来说我本地测试过中心扩展大概 20ms动态规划大概 70ms马拉车大概 5ms实测下来和理论分析完全吻合。这种“理论与实际对应上”的时刻才是刷题最有成就感的地方。