【力扣100题】53.最长回文子串

题目描述给你一个字符串 s找到 s 中最长的回文子串。示例示例 1 输入s babad 输出bab 解释aba 同样是符合题意的答案。 示例 2 输入s cbbd 输出bb 约束1 s.length 1000解题思路总览方法核心思想时间复杂度空间复杂度备注暴力枚举枚举所有子串判断是否回文O(n^3)O(1)会超时动态规划dp[i][j] s[i]s[j] dp[i1][j-1]O(n^2)O(n^2)空间较大中心扩展从中心向两边扩展O(n^2)O(1)最常用Manacher马拉车算法O(n)O(n)O(n)最优但复杂一、中心扩展法推荐核心思想回文串是中心对称的。选择一个中心向两边同时扩展遇到不匹配的字符就停止。这样可以找到以该中心为中心的最长回文串。两种情况回文串有两种形态奇数长度中心是一个字符如 “aba”中心是 ‘b’偶数长度中心是两个字符如 “abba”中心是 ‘bb’代码实现classSolution{public:stringlongestPalindrome(string s){intns.size();intans_l0,ans_r0;// 记录最长回文子串的左右边界// 情况1奇数长度回文中心是单字符for(inti0;in;i){intli,ri;// 以 i 为中心// 向两边扩展直到不匹配while(l0rns[l]s[r]){l--;r;}// 此时 [l1, r-1] 是以 i 为中心的回文串// 长度 r - l - 1if(r-l-1ans_r-ans_l){ans_ll1;ans_rr;}}// 情况2偶数长度回文中心是两个相邻字符for(inti0;in-1;i){intli,ri1;// 以 i 和 i1 为中心while(l0rns[l]s[r]){l--;r;}if(r-l-1ans_r-ans_l){ans_ll1;ans_rr;}}returns.substr(ans_l,ans_r-ans_l);}};二、算法流程图以 s “babad” 为例原始字符串b a b a d 索引 0 1 2 3 4 第一步枚举所有可能的回文中心 奇数长度中心每个字符 i0: b - 向两边扩l0,r0 - s[0]s[0]继续 l-1,r1 - 超界停止 回文b长度 1 i1: a - 向两边扩s[1]s[1] - l0,r2 s[0]s[2] - l-1,r3 - 超界停止 回文bab长度 3 i2: a - 同上回文aba长度 3 i3: a - 向两边扩s[3]s[3] - l2,r4 s[2]!s[4]停止 回文a长度 1 i4: d - 向两边扩s[4]s[4]停止 回文d长度 1 偶数长度中心相邻字符对 i0: ba - s[0]!s[1]停止 回文无 i1: ab - s[1]!s[2]停止 回文无 i2: ba - s[2]!s[3]停止 回文无 i3: ad - s[3]!s[4]停止 回文无 最长回文bab 或 aba长度 3以 s “cbbd” 为例原始字符串c b b d 索引 0 1 2 3 奇数长度中心 i0: c - 长度 1 i1: b - 向两边扩s[1]s[1] - l0,r2 s[0]!s[2]停止 回文b长度 1 i2: b - 同上回文b长度 1 i3: d - 长度 1 偶数长度中心 i0: cb - s[0]!s[1]停止 i1: bb - 向两边扩s[1]s[2] - l0,r3 s[0]!s[3]停止 回文bb长度 2 i2: bd - s[2]!s[3]停止 最长回文bb长度 2三、逐行解析对照原题代码stringlongestPalindrome(string s){intns.size();// ans_l 和 ans_r 记录当前找到的最长回文子串的左右边界左闭右开intans_l0,ans_r0;// ---------- 情况1奇数长度回文 ----------// 中心是单字符枚举每个位置作为中心for(inti0;in;i){intli,ri;// 初始中心是字符 s[i]// while 循环只要 l 和 r 都在范围内且 s[l] s[r]就继续扩展while(l0rns[l]s[r]){l--;r;}// 退出循环时[l1, r-1] 是以 i 为中心的最长回文串// 长度 r - l - 1// 如果比当前答案更长就更新if(r-l-1ans_r-ans_l){ans_ll1;ans_rr;}}// ---------- 情况2偶数长度回文 ----------// 中心是两个相邻字符枚举每对相邻字符for(inti0;in-1;i){intli,ri1;// 初始中心是 s[i] 和 s[i1]while(l0rns[l]s[r]){l--;r;}if(r-l-1ans_r-ans_l){ans_ll1;ans_rr;}}// 返回从 ans_l 开始长度为 ans_r - ans_l 的子串returns.substr(ans_l,ans_r-ans_l);}关键点解释语句含义int ans_l 0, ans_r 0;记录最长回文子串的边界ans_l 是起始索引ans_r 是结束索引不包含while (l 0 r n s[l] s[r])扩展条件左边界没越界右边界没越界左右字符相等l--; r;向两边扩展一位ans_l l 1; ans_r r;更新答案l1 是因为退出循环时 l 多减了 1r - l - 1当前回文串的长度s.substr(ans_l, ans_r - ans_l)C 的 substring参数是起始位置和长度四、图解扩展过程以 s babadi 1中心是 a为例 初始状态 li1, ri1 b a b a d ^ 中心 第一次扩展l0, r2 s[0] s[2]? b b? 是 b a b a d ^ ^ l r 第二次扩展l-1, r3 l 0越界停止 最终回文[l1, r-1] [0, 2] bab 长度 r - l - 1 3 - (-1) - 1 3以 s cbbdi 1中心是 bb为例 初始状态 li1, ri12 c b b d ^^ 中心 第一次扩展l0, r3 s[0] s[3]? c d? 否停止 最终回文[l1, r-1] [1, 2] bb 长度 r - l - 1 4 - 0 - 1 3? 错 实际是 [1,3) s[1] 和 s[2]长度 2 注意退出 while 时 l-1, r4 回文边界是 [l1, r-1] [0, 3]长度 3? 不对 实际 l0 时已经判断 s[0]!s[3]所以回文不包括 0 和 3 正确[1, 3) 不包括 r五、复杂度分析维度分析时间复杂度最坏情况下每个中心都要扩展 O(n) 次共 O(n) 个中心总 O(n^2)空间复杂度只用了几个整数变量O(1)最坏情况字符串是全相同字符如 “aaaaa…”奇数中心每个扩展 O(n) 次偶数中心每个扩展 O(n) 次总计 O(n^2)六、动态规划解法对比思路定义dp[i][j] s[i…j] 是否是回文串。状态转移dp[i][j] (s[i] s[j]) dp[i1][j-1]即首尾相等且中间也是回文classSolution{public:stringlongestPalindrome(string s){intns.size();if(n1)returns;vectorvectorintdp(n,vectorint(n,0));intstart0,maxLen1;// 所有单字符都是回文for(inti0;in;i)dp[i][i]1;// 枚举长度for(intlen2;lenn;len){for(inti0;ilenn;i){intjilen-1;if(s[i]s[j]){if(len2)dp[i][j]1;// aa 这种elsedp[i][j]dp[i1][j-1];}if(dp[i][j]lenmaxLen){starti;maxLenlen;}}}returns.substr(start,maxLen);}};两种方法对比维度中心扩展动态规划时间复杂度O(n^2)O(n^2)空间复杂度O(1)O(n^2)编码难度简单中等思维难度易理解需理解 DP 状态定义七、Manacher 算法了解即可核心思想O(n) 时间复杂度的算法利用回文串的对称性避免重复计算。// 伪代码不完整实现stringmanacher(string s){// 1. 插入分隔符使奇偶统一string t#;for(charc:s){tc;t#;}// 2. 计算每个位置的回文半径vectorintp(t.size(),0);intcenter0,right0;for(inti0;it.size();i){intmirror2*center-i;if(iright)p[i]min(p[mirror],right-i);// 中心扩展while(i-p[i]0ip[i]t.size()t[i-p[i]]t[ip[i]]){p[i];}// 更新 center 和 rightif(ip[i]right){centeri;rightip[i];}}// 3. 找出最长回文// ...}面试中如果能提到 Manacher可以加分但中心扩展已经足够。面试追问 FAQ问题回答要点Q: 为什么中心扩展能找所有回文子串任何回文串都有中心单字符或双字符枚举所有可能的中心扩展找最长Q: 如何处理奇数和偶数两种情况分别处理奇数中心是单字符偶数中心是相邻字符对Q: 时间复杂度为什么是 O(n^2)有 O(n) 个中心每个中心最多扩展 O(n) 次Q: 能用滑动窗口吗不行因为回文长度不确定无法用滑动窗口优化Q: 如果要返回所有最长回文怎么办在遍历过程中记录所有等长的回文而不是只更新一个Q: Manacher 算法了解吗可以简单说O(n) 算法利用回文对称性用半径数组避免重复计算相关题目题目编号题目名称难度核心差异5最长回文子串中等基础题返回子串516最长回文子序列中等返回长度或子序列不要求连续647回文子串中等计数所有回文子串409最长回文串简单可以重新排列字符1312让字符串成为回文串的最少插入困难插入最少字符使字符串回文总结要点内容核心思想中心扩展枚举每个可能的中心单字符或双字符向两边扩展找最长两种情况奇数长度单中心和偶数长度双中心时间复杂度O(n^2)空间复杂度O(1)关键点注意边界条件while 循环结束后 l 多减了 1易错点偶数中心时初始化是 li, ri1不是 li-1, ri1中心扩展法是最直观、最实用的解法面试中推荐使用。如果面试官问更优解可以补充 Manacher 算法的思想。