回文子串这四个字在我刚开始刷 LeetCode 的时候曾经是噩梦。什么“最长回文子串”“回文子串个数”“分割回文串”题目看着都不长真上手就是各种超时和数组越界。后来花了一整周专门拉通这个专题发现它其实是字符串算法里套路感最强的一类只要吃透中心扩展、动态规划回文表和马拉车算法这三板斧大部分回文题都能在五分钟内定出解法框架。这篇笔记是我自己在 Java 环境下的完整刷题总结从最朴素的暴力思路讲起一直推到 O(n) 的马拉车解法每个关键步骤都配了完整的 Java 代码和踩坑记录。内容覆盖 LeetCode 第 5 题、第 647 题、第 131 题这些高频题也顺带整理了相关变种题的练习思路。适合正在刷 LeetCode 热门 100 题、准备 Java 后端面试或者想系统补一补字符串算法的同学直接拿去对照复习。1. 回文子串题的本质三种问法一条底层能力1.1 先理解“回文子串”到底在考察什么回文串的定义很简单一个字符串正着读和倒着读完全一样比如aba、aa、abba都是回文串而ab、abc不是。回文子串问题就是在给定字符串s中找出所有满足这个性质的连续子串s[i..j]。面试官喜欢拿这类题来面是因为它一个题目同时压中了好几个基本功双指针思想、动态规划状态设计、递归回溯的切割逻辑以及字符串索引的精细控制。你只要有一个环节不扎实代码就会在边界条件上翻车。而且这类题可以用多种解法做不同解法的复杂度差异很大很能考察候选人对“暴力解法为什么慢”“如何通过空间换时间”的理解程度。实际面试里回文子串的出现频率远高于你的想象。你翻一下 LeetCode 热门 100 题里面至少有五六道题和回文相关。我做后端开发这些年在多家公司的笔试题里都见过变种有的是判断回文链表有的是求回文子串个数有的是让字符串变成回文串的最小插入次数。核心逃不出这个专题。1.2 高频回文题的三种分类回文子串题目看起来多本质上只有三类问法。我把它们整理成了一张表方便你建立起初步的题型地图。题型代表题目核心解法时间复杂度数所有回文子串的个数LeetCode 647动态规划 / 中心扩展O(n^2)求最长的回文子串LeetCode 5中心扩展 / ManacherO(n^2) / O(n)把字符串拆成全回文子串LeetCode 131 / 132回溯 动态规划预处理指数级 / O(n^2)这三种问法看起来差异很大但它们的底层能力是同一个判断任意子串s[i..j]是否是回文串。只要把这句话想明白接下来所有的解法都是围绕“如何高效完成这个判断”展开的。后面的章节我会按“先基础、再进阶、最后优化”的顺序来写。第二章先说中心扩展法这是理解所有后续解法的基础第三章讲动态规划回文表它专门服务于数个数和分割类问题第四章讲马拉车算法这是追求极致性能的进阶武器最后一章集中讲我在刷题过程中踩过的坑以及一些面试角度的个人心得。2. 中心扩展法最长回文子串的基础解法2.1 暴力解法为什么一定会超时刚开始刷题的人容易写出最直观的暴力版本枚举所有子串s[i..j]再对每个子串调用isPalindrome()方法逐字符判断是否回文。这样出来的代码虽然逻辑没错但复杂度是 O(n^3)因为枚举本身要 O(n^2)每次判断又要 O(n)。以 LeetCode 5 为例题目的字符串长度最多 1000。O(n^3) 在最坏情况下要执行约 10 亿次字符比较在 Java 这种运行环境下几乎不可能通过。即便你能过也说明测试数据太温柔面试官如果追问一句“怎么优化”你还是得回到更优的解法上来。所以暴力代码我建议你只作为思考起点不要真的提交。暴力解法还有一个隐藏问题每次判断回文都重复扫描了大量字符。比如你判断完s[1..5]是回文接着判断s[2..6]时中间的对称关系完全可以用更巧妙的方式复用但暴力写法完全没有利用这一点。2.2 中心扩展的核心思想中心扩展法的出发点很朴素每个回文串都有一个“中心”。奇数长度的回文串中心是一个字符比如aba的中心是b偶数长度的回文串中心是相邻的两个字符比如abba的中心是bb中间这条缝隙。所以我们可以枚举每一个可能作为中心的位置然后从这个中心向左右两边同时扩展只要两侧字符相等就说明回文串还能继续变长一旦遇到两侧字符不同就停下来记录当前中心能扩展出的最大回文长度。注意奇数和偶数两种情况都要枚举。一个字符本身可以看作奇数长度的回文串所以奇数中心就是[i, i]偶数中心则是[i, i1]这对相邻字符。漏掉任何一个都会导致结果偏短。这里有一个很值得品味的关键点中心扩展法把“判断所有子串是否回文”这个问题转换成了“从所有中心出发找最远回文半径”的问题。它的复杂度是 O(n^2)因为中心有大约 2n 个每个中心扩展一次能走多长取决于回文串的长度最坏情况下比如所有字符都相同每个中心都会扩展到字符串边缘。2.3 最长回文子串LeetCode 5 的 Java 完整实现LeetCode 5 要求返回最长回文子串本身。我的实现思路是记录最长回文的起始位置和长度最后用substring截取。完整代码如下class Solution { public String longestPalindrome(String s) { if (s null || s.length() 1) { return ; } int start 0; int maxLen 0; for (int i 0; i s.length(); i) { // 奇数长度回文中心为 i int len1 expandAroundCenter(s, i, i); // 偶数长度回文中心为 i 和 i1 int len2 expandAroundCenter(s, 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 expandAroundCenter(String s, int left, int right) { while (left 0 right s.length() s.charAt(left) s.charAt(right)) { left--; right; } // 循环结束时 left 和 right 比实际回文区间各多跨了一步 return right - left - 1; } }这里最容易被搞错的就是start的推导。假设中心位置是i回文长度是len那么区间应该是[i - (len-1)/2, i len/2]。比如aba中心i1len3起点是1 - (3-1)/2 0如果回文是abba中心取在i2和i13的缝隙位置时我们记录的i其实是左中心字符blen4起点2 - (4-1)/2 0依然正确。这个公式不需要死记画两个例子就能验证。expandAroundCenter返回right - left - 1也是一个经典陷阱。因为while循环退出时left已经多往左移了一位right已经多往右移了一位所以真实回文区间长度应该是(right - 1) - (left 1) 1 right - left - 1。我总是建议小伙伴在本地把这行代码打印一下你会对“退出条件是失败条件”有更深的理解。2.4 中心扩展法的延伸使用中心扩展法不只能求最长回文子串求回文子串个数也非常顺手LeetCode 647 就是一个典型。每当一个中心扩展出长度为len的回文区间就意味着这个中心贡献了一个新的回文子串。枚举所有中心把每次扩展计数累加起来即可。代码如下class Solution { public int countSubstrings(String s) { if (s null || s.length() 0) { return 0; } int count 0; for (int i 0; i s.length(); i) { // 奇数中心 count expandAndCount(s, i, i); // 偶数中心 count expandAndCount(s, i, i 1); } return count; } private int expandAndCount(String s, int left, int right) { int count 0; while (left 0 right s.length() s.charAt(left) s.charAt(right)) { count; left--; right; } return count; } }这个思路比动态规划写起来更简洁也好理解。我第一次做 647 的时候用的动态规划后来发现中心扩展写起来更不容易出错。所以我建议你把两种写法都掌握面试时看情况选用。3. 动态规划回文表数个数与分割问题的通用底座3.1 如何用动态规划判断任意子串是否回文中心扩展法是“按需判断”而动态规划的做法是“一次性预处理”。我们定义一个二维布尔数组dp[i][j]表示子串s[i..j]是否为回文串。状态转移的核心逻辑是一个子串是回文串必须满足两个条件两端字符相等即s.charAt(i) s.charAt(j)去掉两端之后内部子串也是回文串即dp[i1][j-1]为true。但这里有个边界细节当子串长度小于等于 3 时只要两端字符相等内部子串即使只有一个字符或为空也一定是回文。比如aa两端相等内部为空当然是回文aba两端相等内部b是回文。所以转移公式可以写成dp[i][j] s.charAt(i) s.charAt(j) (j - i 2 || dp[i1][j-1])这里j - i 2就包含长度 1、2、3 三种情况非常优雅。这个预处理过程如果能自己想明白其实就是理解了动态规划里“大问题依赖小问题”的思想。你不需要真的去记忆公式抓住“两端相等、内部回文”这个语义随时能自己推出来。3.2 遍历顺序这是最容易写错的地方dp[i][j]依赖的是dp[i1][j-1]也就是“左下角”的格子。如果你用常规的双层循环从i外层、j内层去填表很可能会在计算时发现dp[i1][j-1]还没被算出来。我推荐的遍历方式是把右边界j放在外层左边界i放在内层并且保证i从 0 扫到j。这样在计算dp[i][j]时任何dp[i1][j-1]对应的右边界都是j-1而j-1这个外层循环已经执行过了所以这个值一定已经计算完成。这个遍历顺序我开始也搞反过后来把dp表打印出来才看明白。你调试时可以把表打出来对照多看几遍之后就再也不会错了。3.3 LeetCode 647 回文子串个数的动态规划 Java 实现有了dp表数回文子串个数的逻辑就很简单枚举所有i j的区间只要dp[i][j]为true就计数。完整代码如下class Solution { public int countSubstrings(String s) { int n s.length(); if (n 2) { return n; } boolean[][] dp new boolean[n][n]; int count 0; for (int j 0; j n; j) { for (int i 0; i j; i) { if (s.charAt(i) s.charAt(j) (j - i 2 || dp[i 1][j - 1])) { dp[i][j] true; count; } } } return count; } }很多人会疑惑为什么dp表能数出正确个数。其实你只要想清楚一件事dp[i][j]为true当且仅当s[i..j]是一个回文子串那么把所有这样的区间数一遍自然就是所有回文子串的数量。没有重复也没有遗漏。3.4 分割回文串LeetCode 131 的回溯与 dp 表配合LeetCode 131 要求返回所有可能的分割方案使得每一段都是回文串。这是一个典型的“回溯 切割”问题核心做法是从左到右扫描尝试每个可能的切割位置如果当前这一段是回文就递归处理剩余部分。判断“当前这一段是否回文”如果每次都重新判断会非常浪费。正确的做法是先用 3.1 中的dp表把回文信息全部算好然后在回溯过程中直接用dp[start][end]判断。这样回溯的重点就放在“枚举所有切割方案”上而不是反复做字符串字符比较。完整 Java 代码如下class Solution { public ListListString partition(String s) { ListListString res new ArrayList(); if (s null || s.length() 0) { return res; } int n s.length(); boolean[][] dp new boolean[n][n]; for (int j 0; j n; j) { for (int i 0; i j; i) { if (s.charAt(i) s.charAt(j) (j - i 2 || dp[i 1][j - 1])) { dp[i][j] true; } } } backtrack(s, 0, dp, new ArrayList(), res); return res; } private void backtrack(String s, int start, boolean[][] dp, ListString path, ListListString res) { if (start s.length()) { // 必须新建列表否则 res 里的引用会被后续修改影响 res.add(new ArrayList(path)); return; } for (int end start; end s.length(); end) { if (dp[start][end]) { path.add(s.substring(start, end 1)); backtrack(s, end 1, dp, path, res); // 回溯的关键撤销刚才的选择 path.remove(path.size() - 1); } } } }这里有一个新手很容易忽略的细节res.add(new ArrayList(path))必须拷贝一份而不是直接res.add(path)。因为path这个列表在后续回溯过程中还会被反复修改如果直接加入res最后所有结果都会变成同一个空列表或最后一个状态。这个错误我印象很深因为我在刚开始刷回溯题时几乎每道题都踩一遍。path.remove(path.size() - 1)是回溯的标准动作。你在添加一个子串、进入递归、返回之后必须把这一层添加的内容移除才能继续尝试下一个切割点。如果你漏了这一步path会越积累越长结果五花八门而且非常难调试。3.5 dp 表和回溯组合的复杂度思考dp 预处理本身是 O(n^2) 的时间和 O(n^2) 的空间。回溯部分真正的耗时取决于有多少种分割方案。最坏情况下比如字符串是aaaa任意切割都是回文方案数是 2^(n-1)也就是指数级的这在题目范围内是允许的因为 LeetCode 131 要求返回所有方案方案本身就有这么多。面试官如果继续追问“只求最小切割次数”那就是 LeetCode 132 的范畴可以在 dp 回文表基础上再做一层一维 dp复杂度降到 O(n^2)。不过我建议你先吃透 131 的回溯写法再做 132 就顺理成章了。4. 进阶武器Manacher 算法为什么要学4.1 中心扩展法的瓶颈在哪里中心扩展法看起来已经不错了但它最坏情况下是 O(n^2)。比如字符串是aaaaaaaaaa这种全相同字符每个中心都要扩展到字符串边缘大量的重复比较让人肉疼。有没有可能利用回文的对称性把已经计算过的回文半径“复制”给后面的位置这正是 Manacher 算法马拉车算法的核心思想。我第一次看马拉车算法时觉得它很玄乎后来拆开来看发现它其实只做两件事一是通过插入分隔符让所有回文串都变成奇数长度二是维护一个“最右回文边界”和“中心”利用对称性快速给当前位置一个初始半径。理解这两件事算法就基本掌握了。4.2 预处理插入分隔符把问题统一成奇数长度在 Manacher 算法里我们先把原始字符串每个字符的两边都插入一个不会出现在原串中的分隔符比如#。例如aba变成#a#b#a#abba变成#a#b#b#a#。为什么要这么做因为原始回文串有奇偶两种中心插入分隔符后无论原回文是奇数长度还是偶数长度新串里的回文中心都落在字符上或#上整个串的回文半径统一成奇数长度。这样代码只需要处理一种情况不需要像中心扩展法那样分别调用两次。还要注意原串和新串的下标换算。新串的下标i对应原串中的下标i / 2不完全对因为新串长度为2n1。我们在实现时通常不直接依赖这个换算而是最后通过中心下标和半径反推原串起点这个后面细说。4.3 算法核心回文半径数组、中心 C 与右边界 R定义数组p[i]表示新串中以第i个字符为中心能扩展到的最远回文半径长度。注意这里“半径”指的是从中心向外扩展的步数不算中心自己。例如新串#a#b#a#中心b的下标是 3p[3] 3表示左右各能扩展 3 步覆盖整个#a#b#a#。同时维护两个变量C当前已知最右回文子串的中心R当前已知最右回文子串的右边界也就是C p[C]。当我们扫描到一个新位置i时如果i R说明i在当前已知的最右回文串内部。根据回文对称性i关于中心C的镜像位置mirror 2 * C - i的回文半径p[mirror]可以部分复用。但由于镜像位置的半径可能越过R的边界所以初始值只能取Math.min(R - i, p[mirror])。这句是马拉车算法最精华的一行理解它整个算法就通了。举个例子新串#a#b#b#a#扫描到中心C右边某个位置时如果镜像位置的回文半径已经完全包含在C的回文区间内那么当前中心至少也有同样大的半径如果镜像半径越过R那就只能先保守地从R - i开始再继续向外暴力扩展因为R以外的信息还没被验证过。4.4 最长回文子串的 Manacher Java 实现下面是我自己整理的 Java 实现已经把越界检查都处理好了。这个版本可以直接跑 LeetCode 5也能扩展到求子串个数。class Solution { public String longestPalindrome(String s) { if (s null || s.length() 0) { return ; } // 1. 预处理插入分隔符 StringBuilder sb new StringBuilder(#); for (char ch : s.toCharArray()) { sb.append(ch).append(#); } String t sb.toString(); int n t.length(); int[] p new int[n]; int C 0; int R 0; int maxLen 0; int centerIndex 0; for (int i 0; i n; i) { // 2. 利用对称性初始化 p[i] if (i R) { int mirror 2 * C - i; p[i] Math.min(R - i, p[mirror]); } // 3. 尝试继续向外扩展 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; } // 4. 更新最右边界 C 和 R if (i p[i] R) { R i p[i]; C i; } // 5. 记录最长回文信息 if (p[i] maxLen) { maxLen p[i]; centerIndex i; } } // 6. 由新串下标反推原串起点 int start (centerIndex - maxLen) / 2; return s.substring(start, start maxLen); } }我在写第 3 步时有一个容易出错的地方left和right的初始值是i - (p[i] 1)和i (p[i] 1)意思是先从已经确认的半径外一步开始试探。如果你写成i - p[i]就会把中心字符自己也重复比较一次导致半径偏大。调试时用abba这种例子一眼就能看出来。最后一步的起点换算新串中回文子串的起点是centerIndex - maxLen因为maxLen就是回文半径也是原串回文长度中心左边半径那么多位置内的字符都是回文的一部分。而在插入了#之后原串下标和新串下标的关系是原串下标 新串下标 / 2的整数部分严谨地说是用这个公式。这里直接(centerIndex - maxLen) / 2就可以得到原串起点。我在本地跑过babad、cbbd、aaaa结果都正确你可以放心用。4.5 马拉车算法的复杂度与适用范围马拉车的时间复杂度是 O(n)因为虽然每个位置都可能触发 while 扩展但总的扩展次数是有限的R这个右边界只增不减整体最多向后移动 n 次。空间复杂度 O(n)。不过我需要提醒一点马拉车算法在面试时并不是必考项。大多数大厂的面试题O(n^2) 的解法已经完全够用。如果你的目标是把 LeetCode 热门 100 题刷完马拉车可以放到后面慢慢看先把中心扩展和动态规划写熟练更重要。但如果你面的是对算法复杂度要求很高的团队或者面试官明确追问“能不能做到 O(n)”这时马拉车就是你展示实力的加分项。我个人是把马拉车当作“专题里的最后一块拼图”来学的学完之后再回头看中心扩展法会明显感觉到思路上的升华从“重复计算”到“利用对称性复用”这种优化思想其实在 KMP、Next 数组里也很常见。5. 刷题过程中的常见坑与面试心得5.1 边界条件清单强烈建议背下来回文子串题出错十有八九是边界条件。下面这张表是我反复踩坑之后整理出来的每次写完代码我都会照着快速过一遍。场景易出错点处理建议空字符串下标访问越界开头判断 s null单字符返回值应为自身/1单独处理或确保循环能覆盖全相同字符如aaaa中心扩展最坏 O(n^2)马拉车或接受 dp 解法奇数长度回文中心枚举漏掉单点按[i,i]和[i,i1]两种中心枚举偶数长度回文起点公式算错用i - (len-1)/2推导并本地验证substring区间结束索引写错substring(start, start maxLen)是左闭右开比如 LeetCode 5输入a时如果你的代码没有做空串判断就直接substring会抛StringIndexOutOfBoundsException输入ac时最长回文子串应该返回a或c都可以但如果你没有把单字符中心纳入枚举就会拿到空串。5.2 Java 实现中的几个容易忽略的性能与语法细节第一substring在 Java 7 之后是拷贝字符数组的时间复杂度 O(n)不是 O(1)。如果在一个热循环里反复截取大量子串会有不小的开销。在 LeetCode 131 这类回溯题里为了生成结果必须调用substring这是不可避免的但在中心扩展求最长回文时我建议不要每次更新都截一次而是只记录起点和长度最后截取一次。第二charAt和toCharArray的选择。在读多不写少的场景两者差距不大。但如果你要在一个很长的字符串上频繁按索引取字符比如马拉车算法的 while 循环我个人习惯先转成char[]数组访问arr[i]比反复调用s.charAt(i)稍快而且代码写起来更简洁。你在力扣上能看到很多 Java 高手都是这么干的。第三boolean[][] dp的默认值是false不需要手动初始化。但要注意只有被你显式赋值true的位置才表示回文没赋值的位置就是false。千万别写dp[i][j] dp[i1][j-1]这种式子因为dp表示的是“是回文”而不是“长度”或其他数值。5.3 从回文子串延伸出去的变种题回文子串的底层能力练熟之后你会发现它像一座桥能通向很多其他题目。我把自己做过的相关题按推荐顺序列出来你可以当成一条延伸路线LeetCode 9 回文数最简单整型反转一半注意溢出。LeetCode 234 回文链表快慢指针找中点反转后半段再比较。LeetCode 680 验证回文串 II双指针逼近最多删一个字符时用贪心思路。LeetCode 214 最短回文串要用到 KMP 或马拉车难度较高建议后期挑战。LeetCode 132 分割回文串 II先做回文表再做一维 dp 求最小切割次数。这串题做下来你对“子串类动态规划”和“对称性判断”的敏感度会明显提升。我自己是先刷完 5、647、131 这三个基础题再去做 234 和 680感觉过渡得很自然。面试时如果需要现场推公式回文表这套思路能给足你底气。5.4 一个小技巧本地准备一个回文自测用例集刷这类题时我强烈建议你在本地main方法里准备一组固定用例每次写完算法先跑一遍自测再去力扣提交。我常用的测试集类似这样public static void main(String[] args) { Solution solution new Solution(); String[] tests {, a, aa, ab, aaaa, abac, babad, cbbd}; for (String test : tests) { System.out.println(\ test \ - solution.longestPalindrome(test)); } }这组用例覆盖了空串、单字符、纯偶数回文、纯奇数回文、全部相同字符、混合场景。一个算法只要能跑过这八个输入再去力扣提交基本不会出大问题。这个方法比反复在网页上试错快得多尤其是马拉车这种公式多、起点换算容易错的算法本地打印中间结果能帮你一眼定位问题。最后再分享一个我这半年来反复验证过的体会回文子串题的大部分解法本质上都是在“预计算或者快速判断‘某个子串是否是回文’”。中心扩展是按需扩展动态规划是按长度递推建表马拉车是按对称性复用半径。把这一层想透面试时任何回文变种你都能很快定位到该用哪把钥匙。我自己是在被 131 这道题的数组越界坑过一次认真画出递归树之后才真正把这块吃透的。希望这份笔记能帮你少走点弯路。
