回文子串这个专题我前前后后刷过三轮。第一轮上来就直接做最长回文子串结果被动态规划的状态转移卡到怀疑人生第二轮换了个顺序从统计回文子串数量那道基础题入手才真正体会到中心扩展的妙处第三轮又从源码层面把 Manacher 过了一遍算是把整个专题彻底吃透了。这篇文章就是把这几轮的笔记整理成一份 Java 视角的学习路线适合正在准备面试、刚开始刷 LeetCode 但又被回文类题目搞晕的同学也适合已经会做几道题、想系统梳理一遍思路的人。先说结论回文子串的核心问题就两种——统计有多少个回文子串和找出最长回文子串。围绕这两个问题中心扩展、动态规划、Manacher 是三条最经典的路线。我建议的掌握顺序是中心扩展优先动态规划跟上Manacher 作为进阶理解。下面按照这个顺序把每个思路的代码、推导和坑都过一遍。1. 回文子串题群的共同骨架判定、计数、最长三条主线1.1 从验证回文到枚举子串的思维转变回文串的定义很简单正着读和倒着读一样比如aba、abba。判断一个串是不是回文双指针从两端往中间走就行这是所有回文题的地基。但一旦题目变成这个字符串里有多少个回文子串或者最长的回文子串是多长问题就复杂了。难点在于你需要知道的不再是整串是不是回文而是所有子串里哪些是回文。如果直接枚举所有子串再逐个检查复杂度是 O(n³)n 稍微到几百就明显吃力。所以这个专题真正要解决的核心问题只有一个如何高效地枚举并判断子串是否为回文。从这个问题出发自然衍生出两个方向以每个字符或相邻字符间隙为中心向两边扩展——这是中心扩展法用dp[i][j]记录子串s[i..j]是否是回文——这是动态规划法利用回文的对称性复用之前计算过的回文半径——这是 Manacher 算法。这三条主线其实不是竞争关系而是递进关系。理解它们的共同骨架刷题时就不会觉得每道题都是新题。1.2 三类主流解法的定位与复杂度对比解法核心思想时间复杂度空间复杂度适用规模暴力枚举枚举所有子串再双指针验证O(n³)O(1)n ≤ 100 左右只适合热身中心扩展枚举 2n-1 个中心向两边同步扩展O(n²)O(1)n ≤ 5000 时也还能跑动态规划用布尔表记录子串回文状态逐步推导O(n²)O(n²)n ≤ 5000主要问题是空间Manacher利用对称性复用回文半径O(n)O(n)n 到 10⁵ 以上也不怕这里有个经验之谈如果面试中不特别说明数据范围给一个 O(n²) 的中心扩展完全够用而且它空间 O(1)代码又短是面试时最不容易出错的方案。Manacher 更多是作为你知不知道还有更优解的加分项后面我会专门讲。2. 中心扩展法最推荐优先掌握的解法2.1 为什么枚举中心不会重复也不会漏中心扩展法有个天然的数学优势任意一个回文子串都有且只有一个对称中心。奇数长度的回文子串中心是某个真实字符比如aba的中心是b偶数长度的回文子串中心是两个相邻字符之间的空隙比如abba的中心在b和b之间。所以对于一个长度为 n 的字符串可能的中心一共有 2n-1 个n 个字符中心加上 n-1 个空隙中心。枚举每一个中心从半径 0 开始向左右扩展每次扩展成功就产生一个新的回文子串。因为每个子串的中心唯一不同中心扩展出来的结果不可能重复又因为所有中心都被枚举到了所以也不可能漏掉任何一个回文子串。这个不重不漏的性质是所有回文子串计数题能放心使用中心扩展的根本保证。2.2 统计回文子串数量的完整 Java 实现以 LeetCode 的回文子串计数题为例完整代码如下public int countSubstrings(String s) { int n s.length(); int ans 0; for (int i 0; i n; i) { ans expand(s, i, i); // 奇数长度中心 ans expand(s, i, i 1); // 偶数长度中心 } return ans; } private int expand(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; }这里的expand返回的是以当前中心能扩展出多少个回文子串而不是最长扩展距离。因为每向外扩一步成功就代表一个新的回文子串诞生。例如s aba以i 1字符b为中心时expand(aba, 1, 1)会先数出b再数出aba返回 2。我自己最多犯的一个错误是忘记奇数中心和偶数中心要分开调用。expand(s, i, i)处理单字符中心expand(s, i, i 1)处理双字符间隙中心两个都不能少否则像aa、abba这种偶数长度回文就全漏了。2.3 常见误区中心扩展不是一个中心只管一条线有人会把中心扩展写成这样// 错误示范只向左或只向右扩展或者不同步 while (left 0 s.charAt(left) s.charAt(right)) { left--; right; }看起来没错但少了right length的边界判断在偶数中心i 1越界时会抛异常。更常见的问题是想当然地认为每个中心只要扩一次就行忽略了while要持续扩展到边界为止。还有同学会把中心扩展和双指针验证回文搞混。验证回文是左右两端往中间夹中心扩展是中间往左右两边扩散方向完全不同。刷题时如果切不过来建议在代码注释里写清楚这是以中心向外的扩展不是双指针向内的逼近。2.4 从计数到求最长同一个模板的简单变形理解了计数求最长回文子串就是顺手的事。还是枚举 2n-1 个中心只不过expand不再计数而是返回能扩展的最长半径长度然后维护全局最大值和起始下标public String longestPalindrome(String s) { int n s.length(); if (n 2) return s; int start 0, maxLen 1; for (int i 0; i n; i) { int len1 expandLen(s, i, i); int len2 expandLen(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 expandLen(String s, int left, int right) { while (left 0 right s.length() s.charAt(left) s.charAt(right)) { left--; right; } return right - left - 1; }注意这里expandLen返回的是right - left - 1因为最后跳出循环时左右指针都多走了一步。以s aba为例中心i 1从左1、右1 开始第一次匹配后 left0、right2第二次匹配后 left-1、right3循环结束right - left - 1 3 - (-1) - 1 3正好是aba的长度。起始下标start i - (len - 1) / 2这个公式奇数偶数都适用。比如abba的偶数中心i 1、i 1 2扩展出长度为 4 的回文start 1 - (4 - 1) / 2 0正确。3. 动态规划版本布尔表的填充顺序是硬约束3.1 状态定义与转移方程的由来中心扩展虽然好用但面试官经常会追问一句能不能用动态规划做 这时候你需要能熟练写出第二种方案。定义状态dp[i][j]表示s[i..j]这一段子串是否为回文。它是一个布尔值true 表示回文。转移方程如下dp[i][j] (s[i] s[j]) (j - i 2 || dp[i 1][j - 1])这个方程的逻辑很直观如果首尾字符相等并且去掉首尾后的内部子串也是回文那么整个子串就是回文。关键在于j - i 2这个条件它覆盖了三种不需要查内部状态的短串长度为 1i j单字符天然回文长度为 2如aa首尾相等即回文长度为 3如aba首尾相等中间只剩一个字符一定回文。如果不加j - i 2长度为 2 时会去访问dp[i1][j-1]此时左边界大于右边界在二维表里是无效位置长度为 3 时会访问dp[i1][i1]虽然合法但会让逻辑变得绕。所以这道题的题解普遍建议用j - i 2 || dp[i1][j-1]的写法。3.2 外层循环为什么必须是右边界或长度这是 DP 写法里最大的坑。因为dp[i][j]依赖dp[i1][j-1]也就是说要计算某个状态必须保证左边界加 1、右边界减 1 的那个状态已经被算过。正确的遍历方式有两种方式一外层遍历右边界 j。public int countSubstrings(String s) { int n s.length(); boolean[][] dp new boolean[n][n]; int ans 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; ans; } } } return ans; }方式二外层遍历子串长度。public int countSubstrings(String s) { int n s.length(); boolean[][] dp new boolean[n][n]; int ans 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 3 || dp[i 1][j - 1])) { dp[i][j] true; ans; } } } return ans; }很多初学者第一次写会直觉地写成外层 i 从 0 到 n内层 j 从 i 到 n。这种写法算dp[i][j]时dp[i1][j-1]对应的行i1还没开始遍历永远是 false于是所有长度大于 3 的回文子串全部漏判。我在早期刷题时就在这个坑里蹲了很久最终的解决办法就是背下外层 j 递增内层 i 从 0 到 j这个顺序同时心里默念右边的先算左下角的依赖自然就有。3.3 一维滚动数组的写法与雷区二维布尔表有 O(n²) 空间n 到 5000 时差不多 2500 万个 booleanJava 里 boolean 数组实际按 1 字节算也要 25 MB 左右能接受但不算优雅。用一维滚动数组可以把空间压到 O(n)。思路是外层 j 递增时只需要保留上一轮j-1的结果。关键代码public int countSubstrings(String s) { int n s.length(); boolean[] dp new boolean[n]; int ans 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])) { dp[i] true; ans; } else { dp[i] false; } } } return ans; }注意这里内层 i 是从 0 到 j 正向遍历的。为什么因为计算dp[i]时需要的dp[i1]必须还是上一轮j-1的结果而正向遍历时i1还没被当前轮更新所以取到的是旧值正好是二维写法里的dp[i1][j-1]。如果内层循环写成从j到0反向遍历计算dp[i]时dp[i1]已经被当前轮更新过了取到的就变成了dp[i1][j]语义完全错掉结果会多算或漏算回文子串。这是我实测踩过的坑印象很深。4. Manacher 算法理解对称臂之后面试讲深不吃亏4.1 为什么要学一个看起来用不上的线性算法先说结论绝大多数 LeetCode 题目的字符串长度不超过 1000 或 2000O(n²) 的解法提交完全没有问题。但数据规模一旦到 10⁵比如某些竞赛题O(n²) 就会超时Manacher 是线性 O(n) 的解法。面试中直接要求手写 Manacher 的岗位不算多但面试官可能会问一句最长回文子串有没有 O(n) 的解法 这时你哪怕讲不清细节也要能说出核心思想插入分隔符统一奇偶长度利用回文的对称性复用之前计算过的回文半径。4.2 预处理串与臂长数组的含义Manacher 第一步是把原串s变成一个新串在每两个相邻字符之间插入#并在开头加^、结尾加$两个不相同的哨兵字符。比如aba变成^ # a # b # a # $为什么要插入#因为原串的偶数长度回文没有中心字符不好处理。插入后所有回文都变成以某个字符为中心统一成奇数长度。哨兵^和$的作用是让扩展循环在到达边界时自然停止不用显式判断越界。定义数组p[i]表示新串中以 i 为中心向两边扩展的臂长。比如上面的新串中中心是下标 4 的b它能扩展出#a#b#a#臂长 p[4] 3而原串的aba长度正好也是 3。在这个算法里p[i]的最大值就是原串最长回文子串的长度。4.3 利用对称性省掉重复比较这是 Manacher 最核心的一步。维护两个变量center是当前已知最右回文的中心right是它能到达的最右边界。当我们遍历到某个位置 i 时如果 i 在right之内就一定能在当前已处理的回文段里找到它的对称位置mirror 2 * center - i。由于回文对称性mirror位置的臂长p[mirror]可以借给 i。但要注意一个问题mirror的臂长信息可能超出当前right的范围限制所以 i 的初始臂长不能超过right - ip[i] min(p[mirror], right - i)取完初始值后再继续向两边扩展比较t.charAt(i p[i] 1)和t.charAt(i - p[i] - 1)直到字符不相等。这就是为什么这个算法线性每个位置的臂长只扩展有限次right本身是单调右移的总的字符比较次数是 O(n) 级别。4.4 Java 完整实现与验证用例public String longestPalindrome(String s) { if (s null || s.length() 0) return ; StringBuilder sb new StringBuilder(^); for (char c : s.toCharArray()) { sb.append(#).append(c); } sb.append(#$); String t sb.toString(); int n t.length(); int[] p new int[n]; int center 0, right 0; int maxLen 0, maxStart 0; for (int i 1; i n - 1; i) { int mirror 2 * center - i; if (i right) { p[i] Math.min(right - i, p[mirror]); } while (t.charAt(i p[i] 1) t.charAt(i - p[i] - 1)) { p[i]; } if (i p[i] right) { center i; right i p[i]; } if (p[i] maxLen) { maxLen p[i]; maxStart (i - maxLen) / 2; } } return s.substring(maxStart, maxStart maxLen); }我建议手写几遍这个实现重点体会两个地方一是p[i] Math.min(right - i, p[mirror])这一行借用但不越界的取值逻辑二是最后maxStart (i - maxLen) / 2的换算它把新串下标映射回原串下标。验证一下aba预处理后中心b的下标为 4p[4] 3maxStart (4 - 3) / 2 0返回aba。abba预处理后中心是中间插入的#下标为 5可以推出 p[5] 4maxStart (5 - 4) / 2 0返回abba。两个用例都能对上。5. 变式题与边界条件回文专题里最容易踩的坑5.1 删除一个字符后能否成为回文的双指针思路这个变式题很经典条件从是不是回文变成最多删一个字符后能不能是回文。暴力做法是枚举删除哪个字符复杂度 O(n²)最优做法还是双指针。先正常从两端向中间找第一对不匹配的位置l和r。此时有两种补救方式删掉s[l]继续验证[l1, r]是否回文或者删掉s[r]继续验证[l, r-1]是否回文。只要两条路径有一条成功就返回 true。public boolean validPalindrome(String s) { int left 0, right s.length() - 1; while (left right s.charAt(left) s.charAt(right)) { left; right--; } if (left right) return true; return isRangePalindrome(s, left 1, right) || isRangePalindrome(s, left, right - 1); } private boolean isRangePalindrome(String s, int left, int right) { while (left right) { if (s.charAt(left) ! s.charAt(right)) return false; left; right--; } return true; }这个解法的核心是遇到第一个不匹配点时把删左和删右两种情况都试一次而不是继续在原来的双指针循环里纠结。我第一次写的时候犯过错误只尝试删左边或只删右边导致abca这类用例死活过不了。5.2 输出所有回文子串时的裁剪开销如果题目从计数变成输出所有回文子串列表中心扩展依然适用只需要在扩展成功时把s.substring(left, right 1)加入结果private void expandCollect(String s, int left, int right, ListString res) { while (left 0 right s.length() s.charAt(left) s.charAt(right)) { res.add(s.substring(left, right 1)); left--; right; } }这里有个容易忽略的性能细节Java 的substring在较新版本里是 O(len) 的字符串复制操作。回文子串数量本身可能达到 O(n²)如果每个子串长度又很可观总复制开销就变成 O(n³)。所以只用计数时中心扩展是 O(n²)一旦要求输出全部子串复杂度会上涨这是题目本身的性质决定的不是算法不够好。如果题目还要求去重放心因为每个回文子串中心唯一中心扩展天然不会重复不需要额外 Set。5.3 回文子串和回文子序列是两个不同的 DP很多同学刷完回文子串又去做最长回文子序列题目发现中心扩展完全套不上这是正常的。子串要求连续子序列只要求字符顺序一致不需要连续。子序列 DP 的状态转移是s[i] s[j] 时dp[i][j] dp[i 1][j - 1] 2 s[i] ! s[j] 时dp[i][j] Math.max(dp[i 1][j], dp[i][j - 1])这个 DP 不是布尔表而是长度表逻辑完全不同。建议把这两类题分开整理不要混在一个模板里记否则做题时很容易把连续这个隐含条件丢掉。5.4 边界用例清单不管用哪种解法提交前先跑一遍下面的用例用例期望结果主要检查点s 计数为 0返回空串空串越界处理s a计数为 1最长串为a单字符中心s aa计数为 3最长串为aa偶数长度回文是否漏掉s aaaa计数为 10最长串为aaaa全相同字符不重复计算s abcba最长串为abcba奇数长度中心扩展正确性s abac最长串为aba非回文串边界情况尤其是aaaa计数应为 4 3 2 1 10。我每次写完回文子串计数题都会先拿这个用例跑一遍它能同时暴露中心扩展漏偶数和 DP 填表方向错误的问题。6. 复盘我按什么顺序刷完回文专题6.1 第一阶段先用中心扩展把模板写到肌肉记忆我的建议是把统计回文子串数量这道题作为专题入口因为它代码最短、思路最直观适合用来建立信心。第一天就把中心扩展模板抄三遍以上直到不需要思考就能写出expand函数并且能主动回答为什么奇数偶数的中心都要枚举。第二天再去做最长回文子串你会发现只是把返回值从计数改成长度再把起始下标换算出来。同一个模板打两题印象会非常牢固。6.2 第二阶段动态规划跟着填表顺序反复练DP 部分不用贪多关键是吃透那一个转移方程和两个遍历写法。我会在纸上画一个 5×5 的表格把abcba手工填一遍标出哪些格子先填、哪些后填观察依赖方向。只有亲眼看到dp[i][j]依赖dp[i1][j-1]才会真正理解为什么外层不能按左边界 i 枚举。6.3 第三阶段Manacher 只求讲得清、写得对Manacher 我没有要求自己背而是分三步走第一步只看代码和注释搞清楚center、right、mirror三个变量分别代表什么第二步自己画一个长一点的例子手动模拟abacaba的整个遍历流程第三步合上书凭理解重新实现一遍遇到卡壳的地方再对照原实现。面试时如果被问到最长回文子串我一般这样组织回答先说暴力解 O(n³)再说中心扩展 O(n²)然后主动提一句如果 n 很大还有 Manacher 的 O(n) 解法核心是利用回文对称性复用半径。这样既有梯度又能展示你对这个专题的理解深度。最后再分享一个小习惯我每次写回文相关题目都会先在心里默念三件事——中心扩展要区分奇偶中心、DP 填表外层按右边界或长度、substring类操作注意复制开销。把这三个点记死回文子串这个专题的绝大多数坑就都绕开了。
