回文侦探：三种境界破解最长回文子串

回文侦探：三种境界破解最长回文子串

LeetCode 5. 最长回文子串—— 从暴力到线性，看懂回文问题的三种解题境界。

一、故事开场：你是回文侦探

想象你接到一个任务：在一串字符里，找出最长的"镜像文字"。

比如"babad"里，"bab"和"aba"都是回文 —— 正着读反着读都一样。

你的目标是：在所有回文子串中，找到最长的那个。

但字符串可能有 1000 个字符，肉眼扫描？不现实。

这就是 LeetCode 第 5 题 ——最长回文子串。它看似简单，却藏着三种截然不同的解法境界。

二、暴力解法：为什么不直接枚举？

最笨的方法：枚举所有子串，判断是不是回文。

• 子串数量：O(n2)O(n^2)O(n2)
• 判断回文：O(n)O(n)O(n)
• 总时间：O(n3)O(n^3)O(n3)

面试官听了会摇头。我们需要更聪明的方法。

三、解法一：中心扩展法（面试首选）

核心思路

回文串有个特点：它有一个中心，两边对称。

中心有两种可能：

• 1 个字符（奇数长度，如"aba"）
• 2 个字符（偶数长度，如"abba"）

所以，遍历每个字符，分别作为两种中心，向两边扩展，直到不再对称为止。

下标: 0 1 2 3 4 字符: b a b a d ↑ i=1（中心） 扩展: 左=0, 右=2 → 'b'=='b' ✅ 左=-1, 右=3 → 越界，停！ 得到回文: "bab"，长度 3

代码实现

classSolution{publicStringlongestPalindrome(Strings){if(s==null||s.length()<1)return"";intstart=0,end=0;for(inti=0;i<s.length();i++){intlen1=expand(s,i,i);// 奇数中心intlen2=expand(s,i,i+1);// 偶数中心intlen=Math.max(len1,len2);if(len>end-start){start=i-(len-1)/2;end=i+len/2;}}returns.substring(start,end+1);}privateintexpand(Strings,intleft,intright){while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){left--;right++;}returnright-left-1;// 实际回文长度}}

复杂度

• 时间：O(n2)O(n^2)O(n2)—— 每个中心最多扩展nnn次
• 空间：O(1)O(1)O(1)—— 只记录左右边界

评价

就像一个侦探，从每个可能的中心点开始，向两边展开推理。虽然要查nnn个中心点，但每个案子都不复杂。

四、解法二：动态规划（理解回文的本质）

核心思路

中心扩展是"从中间向两边看"，动态规划则是"从小回文推大回文"。

定义dp[i][j]：子串s[i..j]是否为回文串。

状态转移：

• s[i] != s[j]→dp[i][j] = false（首尾不同，肯定不是）
• s[i] == s[j]→ 看"去掉首尾后"是不是回文
  • 如果子串长度≤2\leq 2≤2（如"a"或"aa"）→ 直接为true
  • 否则dp[i][j] = dp[i+1][j-1]

s = "abba" dp[0][3]: s[0]=='a', s[3]=='a' → 看 dp[1][2] dp[1][2]: s[1]=='b', s[2]=='b' → 长度=2 → true 所以 dp[0][3] = true ✅

遍历顺序很关键：i必须从大到小（因为依赖i+1），j从小到大。

代码实现

classSolution{publicStringlongestPalindrome(Strings){intn=s.length();if(n<2)returns;boolean[][]dp=newboolean[n][n];intstart=0,maxLen=1;for(inti=n-1;i>=0;i--){for(intj=i;j<n;j++){if(s.charAt(i)==s.charAt(j)){if(j-i<=2){dp[i][j]=true;}else{dp[i][j]=dp[i+1][j-1];}}if(dp[i][j]&&(j-i+1)>maxLen){maxLen=j-i+1;start=i;}}}returns.substring(start,start+maxLen);}}

复杂度

• 时间：O(n2)O(n^2)O(n2)
• 空间：O(n2)O(n^2)O(n2)—— 需要二维数组

评价

就像建立一个"回文档案库"，把每个小片段的回文性质都记录下来。当你想知道一个大片段是不是回文时，只需要查档案，而不需要重新验证。

五、解法三：马拉车算法（Manacher）—— 线性时间的奇迹

核心思路

前面两种方法都是O(n2)O(n^2)O(n2)，能不能更快？

马拉车算法做到了O(n)O(n)O(n)。它的核心思想是：利用回文的对称性，避免重复计算。

但直接处理奇偶长度很麻烦，所以第一步是预处理：在每个字符间插入#，把字符串变成统一奇数长度。

原串: a b b a 处理: # a # b # b # a # 下标: 0 1 2 3 4 5 6 7 8

现在所有回文都是奇数长度，中心只有一个。

算法维护一个"最右边界"right和对应的中心center。当处理位置i时：

• 如果i在right左边，它关于center的对称点mirror已经被算过了，可以直接利用
• 但需要注意边界限制，不能直接照搬

代码实现

classSolution{publicStringlongestPalindrome(Strings){if(s==null||s.length()<1)return"";// 预处理：插入 #，统一奇偶StringBuildersb=newStringBuilder("#");for(charc:s.toCharArray()){sb.append(c).append("#");}Stringt=sb.toString();intn=t.length();int[]p=newint[n];// p[i] = 以 i 为中心的回文半径intcenter=0,right=0;// 当前最右回文的中心和右边界intmaxLen=0,start=0;// 记录最长回文for(inti=0;i<n;i++){// 1. 利用对称性初始化 p[i]intmirror=2*center-i;// i 关于 center 的对称点if(i<right){p[i]=Math.min(right-i,p[mirror]);}// 2. 尝试继续扩展intl=i-(p[i]+1);intr=i+(p[i]+1);while(l>=0&&r<n&&t.charAt(l)==t.charAt(r)){p[i]++;l--;r++;}// 3. 更新最右边界if(i+p[i]>right){center=i;right=i+p[i];}// 4. 记录最长回文（转回原串坐标）if(p[i]>maxLen){maxLen=p[i];start=(i-p[i])/2;}}returns.substring(start,start+maxLen);}}

复杂度

• 时间：O(n)O(n)O(n)—— 每个字符最多被访问常数次
• 空间：O(n)O(n)O(n)—— 预处理和半径数组

评价

就像一位老练的侦探，不会每次遇到相似线索都从头推理。他会建立"对称档案"：发现 A 和 B 对称，A 的结论可以直接套用到 B 上。这是算法世界里最美的"偷懒"艺术。

六、三种境界对比

选哪个？

• 面试写代码→ 中心扩展法，代码短、空间优、不易出错
• 理解回文本质→ 动态规划，是很多回文类题的基础
• 追求极限性能→ 马拉车算法，但代码复杂，面试一般不考

七、写在最后

回文问题的美，在于它把"对称"这个直觉概念，变成了可以量化的算法。

从中心扩展的直观，到动态规划的系统，再到马拉车算法的优雅，三种解法像三种人生境界：

中心扩展是活在当下，动态规划是积累经验，马拉车则是站在经验的肩膀上飞翔。

但归根结底，最实用的往往是那个看起来"最笨"的中心扩展法 —— 因为它足够简单，足够可靠，就像生活中那些朴实却有效的道理。

简单，往往是最深的功力。

欢迎在评论区分享你的理解，或者指出我表述不清的地方。一起进步！