单看这个标题很多人会以为“回文子串”就是背几道题、刷个二十道就完事。但我在实际准备Java面试的过程中把LeetCode上涉及回文子串的题目翻了个底朝天之后发现这根本不是一道题的事——它是一个可以串起中心扩展法、动态规划、马拉车算法、双指针、字符串哈希的完整知识簇。更重要的是回文子串题的代码量大多不长但每个解法背后的“为什么”非常深几乎覆盖了Java面试八股文里算法部分的所有核心考点。这套笔记是我刷了LeetCode 5、125、409、516、647、214、680以及一系列周赛题之后整理出来的包含完整Java代码、复杂度推导、记忆口诀和踩坑实录分享给正在准备面试的你。1. 内容整体设计与思路拆解1.1 核心需求解析回文子串在LeetCode里是一个“貌似简单、实则遍地是坑”的专题。它主要解决四类问题一是“给定一个字符串找最长的回文子串”二是“统计回文子串的总数量”三是“判断字符串是否为回文”四是“通过添加字符让字符串变成回文”。表面上看每道题的问法不同但底层的核心能力只有一个——判断任意区间[i, j]是不是回文。我复习这个专题时给自己定了一个目标不看题解独立用三种方法解出LeetCode 5最长回文子串。为什么是三种因为只有当你用暴力、中心扩展、动态规划分别写一遍你才会真正理解为什么马拉车算法是O(n)以及面试官问“你还有更好的算法吗”时你要怎么接话。而且这三种解法在Java里的实现细节完全不同比如substring的底层拷贝开销、char[]比String.charAt快多少、二维boolean数组的内存布局这些都是可以深挖的面试点。另外这个专题紧贴Java面试的“基础算法”双重要求字符串处理是Java基础中的基础而回文子串又是算法题中的高频题。把这类题吃透等于同时复习了String底层实现、char[]操作、动态规划状态转移、双指针边界处理性价比很高。1.2 技术方案选型与比较回文子串问题的四个主流解法我在下面的表格里做了一个直接对比。你在面试时必须能快速说出它们的复杂度并针对面试官的追问给出选择理由。解法时间复杂度空间复杂度适用场景面试推荐度暴力枚举所有子串O(n³)O(1)仅作为思路引入不推荐中心扩展法O(n²)O(1)找最长回文子串、统计回文数强烈推荐动态规划O(n²)O(n²)需要配合DP做状态推导的变体题推荐Manacher马拉车O(n)O(n)规模大、对性能有硬性要求加分项暴力法我基本不写但我会用它作为引子来解释“中心扩展为什么快”暴力要枚举所有子串并逐个判断一个长度为n的字符串有大约n²/2个子串每个子串判断回文平均要n/2次比较合起来就是O(n³)。而中心扩展把“枚举所有起点终点”改成了“枚举所有中心点”每个中心点向外扩展的次数就是回文半径最坏情况下是O(n)n个中心点合起来是O(n²)。这就是一个“换种思维方式直接把复杂度降一个量级”的典型案例。2. 回文的核心概念与推导基础2.1 回文的数学本质回文Palindrome的本质是一个字符串满足S[i] S[n-1-i]即正着读和倒着读完全相同。这里有个很容易混淆的细节回文子串和回文子序列的区别。子串必须是连续的比如s abcba中bcb和abcba都是回文子串但子序列不要求连续abca中的aba就是一个回文子序列尽管它不是子串。我复习这个专题时踩过的一个坑是在用双指针判断回文的时候不要直接比较整个子串和它的反转——因为反转整个字符串需要额外O(n)空间正确做法是同时从两端往中间走每一步比较两个字符是否相等。这个“两端夹逼”的思路是可以通用于回文链表、回文数组、验证回文数字等多个场景的。2.2 奇偶长度的对称性回文的核心规律是“中心对称”。这里有两种形态奇数长度回文的中心是一个字符比如aba的中心是b偶数长度回文的中心是空隙比如abba的中心在b和b之间的空隙处。所有回文问题本质上都是围绕这两种中心展开的。我个人的记忆方法是“中心要么是一个点要么是一条缝”。对字符串中的每个位置i我们尝试把它当作奇数中心同时把i和i1之间的缝隙当作偶数中心然后向两边扩展。所以中心总数是2n-1包括n个字符位置和n-1个字符间的缝隙这也是中心扩展法时间复杂度O(n²)的由来。理解了这一点你就会明白为什么有些题解里会在每个字符间插入一个占位符比如#那正是马拉车算法把两种中心统一成一种中心的思路。3. 中心扩展法最实用的一把刀3.1 核心思路推导中心扩展法的思路非常简单枚举每个可能的中心然后向两边扩展。我建议你把它想象成“从每个字符向两边照手电筒看两边字符能同时照亮多长”。代码上分成两段奇数长度回文从(i, i)开始扩展偶数长度回文从(i, i1)开始扩展。有人会问中心扩展法和暴力法都是O(n²)为什么面试推荐用中心扩展关键在于常数因子。暴力法需要三重循环每一层都在做字符串切片和比较实际跑起来非常慢中心扩展只有两层循环内层while平摊下来并不总是O(n)很多情况下扩展不了两步就断了实际运行效率比动态规划还要好。我用LeetCode 5的测试数据验证过中心扩展法的耗时大约是DP解法的1/3到1/2。3.2 Java实现与细节中心扩展法最标准的实现我放在这里public String longestPalindrome(String s) { if (s null || s.length() 2) return s; int start 0, maxLen 0; char[] chars s.toCharArray(); for (int i 0; i chars.length; i) { // 奇数长度中心是一个字符 int len1 expand(chars, i, i); // 偶数长度中心是i和i1之间的空隙 int len2 expand(chars, i, i 1); int len Math.max(len1, len2); if (len maxLen) { maxLen len; start i - (len - 1) / 2; } } return s.substring(start, start maxLen); } private int expand(char[] chars, int left, int right) { while (left 0 right chars.length chars[left] chars[right]) { left--; right; } return right - left - 1; }这里有三个细节我要特别强调。第一为什么要转成char[]我用Java写这道题时一开始直接用s.charAt(i)性能其实也不差但LeetCode的耗时统计很敏感charAt()每次都有越界检查和字符串内部逻辑而char[]的数组下访问几乎是零开销。在反复调用数百万次的场景下这个优化能带来肉眼可见的耗时下降。这不是玄学是实测结果。第二start i - (len - 1) / 2这个公式怎么理解len是回文长度i是中心点位置。奇数长度时(len-1)/2 表示中心到左端点的距离偶数长度时中心i是左半部分的最后一个字符(len-1)/2 往下取整依然能算对左边界。我建议你举两个例子验证sbabad中心i1时len3start0中心i1作为偶数中心时len0。再比如cbbd中心i1作为偶数中心时len2start1-01正确。第三return right - left - 1是因为退出while时left和right已经越过了边界正确的回文区间是(left1, right-1]长度就是right-left-1。这个“先扩展后拦截”的模式在后续很多题里都会遇到比如判断双指针移出边界后又回退。3.3 中心扩展的经验总结中心扩展法在统计回文子串数量LeetCode 647时同样通用只要把每次成功扩展时计数加一就行。有一个我用了很久的“笔算辅助技巧”遇到具体例子时在纸上画出两个中心——字符中心和字符间缝隙中心分别标出扩展边界。比如aaa字符中心0的回文有a一个扩展得到aaa再得一个缝隙中心(0,1)扩展得到aa一共是6个回文子串三个单字符a、两个aa、一个aaa。这个数法比直接背公式可靠得多。4. 动态规划法面试追问的正确回答4.1 状态设计与转移推导动态规划解决回文子串问题最关键的一步是状态定义dp[i][j]表示子串s[i...j]是否为回文。这里我踩过一个大坑二维boolean数组的遍历顺序不能随便来。因为状态转移方程是dp[i][j] (s[i] s[j]) dp[i1][j-1]也就是说dp[i][j]依赖的是dp[i1][j-1]即左下角的格子。如果你按行从上到下、从左到右遍历算dp[0][3]的时候dp[1][2]还没被计算出来。所以必须按长度从小到大的顺序遍历先算长度1和2的子串再算长度3、4……这样每一步依赖的子问题都已经算好了。还有一个细节j - 1 i 1的时候也就是说区间长度小于等于2时只需要判断两个端点相等即可不需要查dp[i1][j-1]否则会数组越界。这个边界条件非常容易漏漏了就是ArrayIndexOutOfBoundsException。4.2 Java实现与空间优化标准的DP解法代码public int countSubstrings(String s) { int n s.length(); boolean[][] dp new boolean[n][n]; int count 0; for (int len 1; len n; len) { for (int i 0; i len - 1 n; i) { int j i len - 1; if (s.charAt(i) ! s.charAt(j)) { continue; } if (len 2 || dp[i 1][j - 1]) { dp[i][j] true; count; } } } return count; }如果你去LeetCode提交DP解法会发现空间复杂度O(n²)在n1000时是1,000,000个booleanJava里boolean数组实际占1字节也就是1MB左右一般能过。但要刷到n5000以上O(n²)空间就非常吃紧了。这时候可以优化成滚动数组因为dp[i][j]只依赖dp[i1][j-1]也就是只需要上一行的dp[i1][j-1]信息。把二维数组压缩成一维遍历时从后往前更新就能保证用到的dp[j-1]是上一次长度迭代的结果。空间降到O(n)。优化后的代码public int countSubstrings(String s) { int n s.length(); boolean[] dp new boolean[n]; int count 0; for (int len 1; len n; len) { for (int i 0; i len - 1 n; i) { int j i len - 1; if (s.charAt(i) s.charAt(j) (len 2 || dp[i 1])) { dp[i] true; count; } else { dp[i] false; } } } return count; }注意这里的dp[i1]必须是从上一次长度迭代里留下来的值所以内层循环不能反向遍历而是要从小到大遍历并且每次要及时复位dp[i]为false否则上一次长度迭代的true会污染本次判断。这个“滚动残留值”的坑是我实打实踩过的特别隐蔽实际跑测试用例时可能会多算出几个回文串。4.3 DP解法适用于哪些变体题目DP解法最吃香的场景是“统计回文子序列”这类题目。LeetCode 516最长回文子序列就是一个典型状态定义变成dp[i][j]表示s[i...j]的最长回文子序列长度转移方程是如果 s[i] s[j]: dp[i][j] dp[i1][j-1] 2 否则: dp[i][j] max(dp[i1][j], dp[i][j-1])注意这里的dp[i][j]不再依赖左下角而是依赖左边和正下方的格子所以遍历顺序是i从n-1到0、j从i1到n-1。我刚开始做这题时还套用回文子串的遍历顺序结果状态引用错了输出全是错的。所以不要死记遍历顺序而是要看转移方程里依赖哪些位置——这是动态规划最重要的“以形定序”思想。5. Manacher算法理解即可掌握加分5.1 核心优化思想Manacher算法国内俗称“马拉车”之所以能做到O(n)核心是通过“对称性复用”避免重复扩展。它先对原字符串做预处理在首尾和每个字符间插入一个特殊分隔符比如#这样无论奇数还是偶数长度的回文统一变成了奇数长度中心点一定是字符可能是#。然后维护一个p[i]数组表示以i为中心的最大回文半径同时维护当前回文的最右边界mx和对应的中心id。算法的关键循环是p[i] mx i ? Math.min(p[2 * id - i], mx - i) : 1;这里有两个含义如果i没超出右边界mx那么i关于id的对称点j 2*id-i的回文半径可以利用但上限不能超过mx-i因为超出mx的部分还未验证只能保守地取较小值。之后以i为中心继续扩展若超过mx则更新id和mx。5.2 Java实现要点public String longestPalindrome(String s) { StringBuilder sb new StringBuilder(#); for (char c : s.toCharArray()) { sb.append(c).append(#); } char[] t sb.toString().toCharArray(); int n t.length; int[] p new int[n]; int center 0, right 0; int maxLen 0, maxCenter 0; for (int i 0; i n; i) { p[i] right i ? Math.min(p[2 * center - i], right - i) : 1; while (i - p[i] 0 i p[i] n t[i - p[i]] t[i p[i]]) { p[i]; } if (i p[i] right) { right i p[i]; center i; } if (p[i] maxLen) { maxLen p[i]; maxCenter i; } } int start (maxCenter - maxLen) / 2; return s.substring(start, start maxLen - 1); }写这个算法时最容易犯的错有三个一是忘记每个回文半径p[i]在插入#后会等于原回文长度加1最后截取时要把半径转换成原字串长度二是数组越界因为扩展时i-p[i]可能为负数ip[i]可能超过nwhile循环前必须判断边界三是在更新最右边界时必须是i p[i] right而不是虽然对最终结果影响不大但会影响计算效率。我在面试中把Manacher放在最后才提并明确告诉面试官不但知道它能做到O(n)而且知道它通过复用对称回文信息来减少冗余扩展。面试官通常对我的印象分会有明显提升因为这个算法写过的人并不多能现场解释清楚“mx和id的作用”本身就是加分项。6. LeetCode高频题目实战拆解6.1 LeetCode 5 最长回文子串这道题是回文子串专题的第一题。我推荐直接用中心扩展法因为代码短、易记忆、不容易出错。LeetCode 5的通过率不高主要原因在于很多新手用暴力O(n³)超时或写DP时遍历顺序不对。我的模板代码已经在3.2节给出直接套用即可。面试时如果要求“尽量优化”再从中心扩展法过渡到Manacher。注意要能解释中心扩展的时间和空间复杂度并说出“最坏情况和平均情况”的区别——很多面试官会追问这一点。6.2 LeetCode 647 统计回文子串这道题等价于“统计所有能扩展成功的中心数”。中心总数是2n-1代码和最长回文子串几乎一样只是把“更新最大长度”改成了“计数1”。我提供一个利用char[] 的计数版本public int countSubstrings(String s) { char[] cs s.toCharArray(); int n cs.length; int count 0; for (int i 0; i n; i) { int odd expandCount(cs, i, i); int even expandCount(cs, i, i 1); count odd even; } return count; } private int expandCount(char[] cs, int l, int r) { int cnt 0; while (l 0 r cs.length cs[l] cs[r]) { cnt; l--; r; } return cnt; }这里有个实用小技巧把“扩展一次计数一次”封装成一个函数代码看起来整洁也便于在笔试时快速验证。如果是现场手写建议直接写到白板上并注明“每个中心扩展成功的次数就是从这个中心产生的回文子串数量”。6.3 LeetCode 125 验证回文串这道题看起来最简单但细节坑非常多。它的要求是只考虑字母和数字字符并且忽略大小写。public boolean isPalindrome(String s) { int left 0, right s.length() - 1; while (left right) { while (left right !isValid(s.charAt(left))) left; while (left right !isValid(s.charAt(right))) right--; if (Character.toLowerCase(s.charAt(left)) ! Character.toLowerCase(s.charAt(right))) { return false; } left; right--; } return true; } private boolean isValid(char c) { return Character.isLetterOrDigit(c); }我在这个题上踩过两个坑第一如果不先过滤非法字符直接双指针比较遇到.,这种标点符号就会报错第二数字字符在Character.toLowerCase下是安全的但不要用A c c Z这种手动范围判断加- a A转换容易把非字母数字的ASCII码搞乱。直接用JDK内置的Character.isLetterOrDigit和toLowerCase既简洁又不容易出错。6.4 LeetCode 516 最长回文子序列这道题的DP思路我在4.3节详细说了。它的核心区别是子序列允许删除字符但保持了字符的相对顺序。遍历顺序从in-1开始j从i1开始因为转移方程依赖左边dp[i1][j]和正下方dp[i][j-1]。我有一个记忆“回文子序列DP”的笨办法把它类比成“字符串和反转字符串的LCS最长公共子序列”。因为s和其反转串rev的最长公共子序列恰好就是s的最长回文子序列。这个等价关系在理解题解时非常有用虽然实际实现时直接用DP转移更高效但如果忘了转移方程靠LCS思路也能把答案写出来。6.5 相关变体214最短回文串、680验证回文串IILeetCode 214最短回文串是一道难度较高、但面试可能出现的题给定一个字符串s可以在前面添加最少字符让它变成回文。核心思路是先求s的最长回文前缀然后把剩下的部分反转拼到前面。求最长回文前缀可以用中心扩展法从0开始扩展也可以用KMP的next数组技巧。我建议用KMP思想把s拼成s # reverse(s)然后求整个拼接串的最长前后缀匹配长度。这里的#分隔符是为了防止匹配越过拼接点。LeetCode 680验证回文串II则是简化版最多删除一个字符判断是否为回文。用双指针一旦遇到不相等的位置分别尝试跳过左边或跳过右边剩下的子串如果是回文就OK。这道题的技巧是不要在原串上截取后再判断而是直接传(left1, right)和(left, right-1)给辅助函数。7. 面试现场常见追问与避坑实录7.1 面试官最爱追问的五个问题我在模拟面试和真实面试中总结出围绕回文子串面试官最常问的问题是中心扩展法为什么不会漏掉答案因为所有回文子串都有一个中心字符或缝隙枚举所有中心并扩展到最大必然覆盖所有回文子串。这句话一定要会说。动态规划和中心扩展你会选哪一种我的回答是场景题优先选中心扩展因为空间O(1)如果题目还要求同时解决“统计数量”的DP变体选DP更自然。如果字符串长度达到10^5怎么办答案是Manacher O(n)而且一定要能说出预处理#和p数组的含义。Java里substring的复杂度你知道吗这个方法返回的是原字符串在堆中的视图JDK7之后是新字符串拷贝char[]的时间是O(n)。所以频繁调用substring会导致额外开销尽量用数组下标代替。字符集假设是什么如果只包含小写字母那么我们可以直接用int[26]做字符频率统计回文串的构造问题就变成了“桶计数”。LeetCode 409最长回文串就是这种思路偶数频率全部加上奇数频率取最大偶数部分再加一个中心。7.2 笔试时的效率优化技巧回文子串题目在Java笔试里我总结了三个公认好用的“加速习惯”优先把String转成char[]。这个习惯在多次重复遍历同一个字符串时收益极高因为charAt每次都要做范围检查虽然JIT可能内联优化但在LeetCode这种短时测试环境下数组访问肉眼可见更快。避免在while循环里反复调用s.length()。把长度提出来作为局部变量代码更清晰也能避免反复方法调用。慎用substring生成大量临时字符串。比如验证回文时不要写if (isPalindrome(s.substring(left, right)))改成传下标参数可以大幅减少内存分配和GC压力。7.3 常见错误速查表我把这个专题里容易翻车的错误整理成一张速查表方便你复习时自查。错误类型具体表现根因与对策DP遍历顺序错输出结果比预期少或多按转移方程确定遍历序回文子串按长度递增回文子序列按i从大到小奇数/偶数中心漏掉最长回文结果偏短记住中心是2n-1个不是n个数组越界报ArrayIndexOutOfBoundsExceptionwhile循环前判断left0 rightlenManacher半径转换错返回结果多算或少算字符记住插入#后p[i]-1才是原回文长度字符过滤遗漏验证回文时对非字母数字比较先过滤或跳过不合法字符再比较滚动数组残留值统计回文数量偏大每次更新后把不需要的dp[i]复位为false7.4 刷题顺序与复盘方法如果你也想把这个专题彻底吃透我建议按这个顺序刷LeetCode 125基础验证→ LeetCode 5最长回文子串→ LeetCode 647统计数量→ LeetCode 680删一字符验证→ LeetCode 409最长回文构造→ LeetCode 516回文子序列→ LeetCode 214最短回文串。每做完一道都要逼自己用“中心扩展法”和“DP”分别实现一遍并且把关键代码默写三遍。我自己的复盘习惯是给每道题建立一张卡片上面写清题目编号、核心思路、复杂度、易错点、与哪些题解法相通。比如647和5是同一套模板516和LCS是等价关系214和KMP关联。这样复习到后期你脑子里会有一个“回文知识图谱”而不是零散的两百多道题。8. 个人经验与后续扩展方向回文子串专题学习到这里我不建议继续沉溺在更多变体题里。我的体会是这个专题最大的价值不在于背下某道题的答案而在于训练一种“如何从多个角度拆解同一个问题”的思维方式暴力枚举、中心扩展、动态规划、马拉车算法其实是对同一个目标不断做优化的四个层次。你在面试里展现出的不是“我会做这道题”而是“我能通过复杂度分析找到当前约束下的最优解”。最后再分享一个我最近才摸索出来的技巧在做字符串类的算法题时要养成“画图模拟”的习惯。很多边界错误都是因为脑子里没有建立区间、中心、右边界这些位置关系。我在白板上画了几次回文半径扩展的图之后Manacher算法的代码就再也没写错过。希望这份笔记能帮你少踩一些坑顺顺利利拿下回文子串相关的每一道题。