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

回文侦探三种境界破解最长回文子串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 个字符奇数长度如aba2 个字符偶数长度如abba所以遍历每个字符分别作为两种中心向两边扩展直到不再对称为止。下标: 0 1 2 3 4 字符: b a b a d ↑ i1中心 扩展: 左0, 右2 → bb ✅ 左-1, 右3 → 越界停 得到回文: bab长度 3代码实现classSolution{publicStringlongestPalindrome(Strings){if(snull||s.length()1)return;intstart0,end0;for(inti0;is.length();i){intlen1expand(s,i,i);// 奇数中心intlen2expand(s,i,i1);// 偶数中心intlenMath.max(len1,len2);if(lenend-start){starti-(len-1)/2;endilen/2;}}returns.substring(start,end1);}privateintexpand(Strings,intleft,intright){while(left0rights.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[i1][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必须从大到小因为依赖i1j从小到大。代码实现classSolution{publicStringlongestPalindrome(Strings){intns.length();if(n2)returns;boolean[][]dpnewboolean[n][n];intstart0,maxLen1;for(intin-1;i0;i--){for(intji;jn;j){if(s.charAt(i)s.charAt(j)){if(j-i2){dp[i][j]true;}else{dp[i][j]dp[i1][j-1];}}if(dp[i][j](j-i1)maxLen){maxLenj-i1;starti;}}}returns.substring(start,startmaxLen);}}复杂度时间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(snull||s.length()1)return;// 预处理插入 #统一奇偶StringBuildersbnewStringBuilder(#);for(charc:s.toCharArray()){sb.append(c).append(#);}Stringtsb.toString();intnt.length();int[]pnewint[n];// p[i] 以 i 为中心的回文半径intcenter0,right0;// 当前最右回文的中心和右边界intmaxLen0,start0;// 记录最长回文for(inti0;in;i){// 1. 利用对称性初始化 p[i]intmirror2*center-i;// i 关于 center 的对称点if(iright){p[i]Math.min(right-i,p[mirror]);}// 2. 尝试继续扩展intli-(p[i]1);intri(p[i]1);while(l0rnt.charAt(l)t.charAt(r)){p[i];l--;r;}// 3. 更新最右边界if(ip[i]right){centeri;rightip[i];}// 4. 记录最长回文转回原串坐标if(p[i]maxLen){maxLenp[i];start(i-p[i])/2;}}returns.substring(start,startmaxLen);}}复杂度时间O(n)O(n)O(n)—— 每个字符最多被访问常数次空间O(n)O(n)O(n)—— 预处理和半径数组评价就像一位老练的侦探不会每次遇到相似线索都从头推理。他会建立对称档案发现 A 和 B 对称A 的结论可以直接套用到 B 上。这是算法世界里最美的偷懒艺术。六、三种境界对比境界算法时间空间核心思想推荐指数凡人暴力枚举O(n3)O(n^3)O(n3)O(1)O(1)O(1)枚举所有子串⭐高手中心扩展O(n2)O(n^2)O(n2)O(1)O(1)O(1)从中心向两边扩展⭐⭐⭐⭐⭐大师动态规划O(n2)O(n^2)O(n2)O(n2)O(n^2)O(n2)小回文推大回文⭐⭐⭐⭐神仙马拉车O(n)O(n)O(n)O(n)O(n)O(n)利用对称性避免重复计算⭐⭐⭐选哪个面试写代码→ 中心扩展法代码短、空间优、不易出错理解回文本质→ 动态规划是很多回文类题的基础追求极限性能→ 马拉车算法但代码复杂面试一般不考七、写在最后回文问题的美在于它把对称这个直觉概念变成了可以量化的算法。从中心扩展的直观到动态规划的系统再到马拉车算法的优雅三种解法像三种人生境界中心扩展是活在当下动态规划是积累经验马拉车则是站在经验的肩膀上飞翔。但归根结底最实用的往往是那个看起来最笨的中心扩展法 —— 因为它足够简单足够可靠就像生活中那些朴实却有效的道理。简单往往是最深的功力。欢迎在评论区分享你的理解或者指出我表述不清的地方。一起进步