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

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

示例

示例 1： 输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。 示例 2： 输入：s = "cbbd" 输出："bb" 约束：1 <= s.length <= 1000

解题思路总览

一、中心扩展法（推荐）

核心思想

回文串是中心对称的。选择一个中心，向两边同时扩展，遇到不匹配的字符就停止。这样可以找到以该中心为中心的最长回文串。

两种情况

回文串有两种形态：

• 奇数长度：中心是一个字符，如 “aba”，中心是 ‘b’
• 偶数长度：中心是两个字符，如 “abba”，中心是 ‘bb’

代码实现

classSolution{public:stringlongestPalindrome(string s){intn=s.size();intans_l=0,ans_r=0;// 记录最长回文子串的左右边界// 情况1：奇数长度回文，中心是单字符for(inti=0;i<n;i++){intl=i,r=i;// 以 i 为中心// 向两边扩展，直到不匹配while(l>=0&&r<n&&s[l]==s[r]){l--;r++;}// 此时 [l+1, r-1] 是以 i 为中心的回文串// 长度 = r - l - 1if(r-l-1>ans_r-ans_l){ans_l=l+1;ans_r=r;}}// 情况2：偶数长度回文，中心是两个相邻字符for(inti=0;i<n-1;i++){intl=i,r=i+1;// 以 i 和 i+1 为中心while(l>=0&&r<n&&s[l]==s[r]){l--;r++;}if(r-l-1>ans_r-ans_l){ans_l=l+1;ans_r=r;}}returns.substr(ans_l,ans_r-ans_l);}};

二、算法流程图

以 s = “babad” 为例

原始字符串：b a b a d 索引： 0 1 2 3 4 第一步：枚举所有可能的回文中心 奇数长度中心（每个字符）： i=0: "b" -> 向两边扩：l=0,r=0 -> s[0]==s[0]，继续 l=-1,r=1 -> 超界，停止 回文："b"，长度 1 i=1: "a" -> 向两边扩：s[1]==s[1] -> l=0,r=2 s[0]==s[2] -> l=-1,r=3 -> 超界，停止 回文："bab"，长度 3 i=2: "a" -> 同上，回文："aba"，长度 3 i=3: "a" -> 向两边扩：s[3]==s[3] -> l=2,r=4 s[2]!=s[4]，停止 回文："a"，长度 1 i=4: "d" -> 向两边扩：s[4]==s[4]，停止 回文："d"，长度 1 偶数长度中心（相邻字符对）： i=0: "ba" -> s[0]!=s[1]，停止 回文：无 i=1: "ab" -> s[1]!=s[2]，停止 回文：无 i=2: "ba" -> s[2]!=s[3]，停止 回文：无 i=3: "ad" -> s[3]!=s[4]，停止 回文：无 最长回文："bab" 或 "aba"，长度 3

以 s = “cbbd” 为例

原始字符串：c b b d 索引： 0 1 2 3 奇数长度中心： i=0: "c" -> 长度 1 i=1: "b" -> 向两边扩：s[1]==s[1] -> l=0,r=2 s[0]!=s[2]，停止 回文："b"，长度 1 i=2: "b" -> 同上，回文："b"，长度 1 i=3: "d" -> 长度 1 偶数长度中心： i=0: "cb" -> s[0]!=s[1]，停止 i=1: "bb" -> 向两边扩：s[1]==s[2] -> l=0,r=3 s[0]!=s[3]，停止 回文："bb"，长度 2 i=2: "bd" -> s[2]!=s[3]，停止 最长回文："bb"，长度 2

三、逐行解析（对照原题代码）

stringlongestPalindrome(string s){intn=s.size();// ans_l 和 ans_r 记录当前找到的最长回文子串的左右边界（左闭右开）intans_l=0,ans_r=0;// ---------- 情况1：奇数长度回文 ----------// 中心是单字符，枚举每个位置作为中心for(inti=0;i<n;i++){intl=i,r=i;// 初始中心是字符 s[i]// while 循环：只要 l 和 r 都在范围内，且 s[l] == s[r]，就继续扩展while(l>=0&&r<n&&s[l]==s[r]){l--;r++;}// 退出循环时：[l+1, r-1] 是以 i 为中心的最长回文串// 长度 = r - l - 1// 如果比当前答案更长，就更新if(r-l-1>ans_r-ans_l){ans_l=l+1;ans_r=r;}}// ---------- 情况2：偶数长度回文 ----------// 中心是两个相邻字符，枚举每对相邻字符for(inti=0;i<n-1;i++){intl=i,r=i+1;// 初始中心是 s[i] 和 s[i+1]while(l>=0&&r<n&&s[l]==s[r]){l--;r++;}if(r-l-1>ans_r-ans_l){ans_l=l+1;ans_r=r;}}// 返回从 ans_l 开始，长度为 ans_r - ans_l 的子串returns.substr(ans_l,ans_r-ans_l);}

关键点解释

四、图解扩展过程

以 s = "babad"，i = 1（中心是 'a'）为例： 初始状态： l=i=1, r=i=1 b a b a d ^ 中心 第一次扩展（l=0, r=2）： s[0] == s[2]? 'b' == 'b'? 是！ b a b a d ^ ^ l r 第二次扩展（l=-1, r=3）： l < 0，越界，停止 最终回文：[l+1, r-1] = [0, 2] = "bab" 长度 = r - l - 1 = 3 - (-1) - 1 = 3

以 s = "cbbd"，i = 1（中心是 "bb"）为例： 初始状态： l=i=1, r=i+1=2 c b b d ^^ 中心 第一次扩展（l=0, r=3）： s[0] == s[3]? 'c' == 'd'? 否，停止 最终回文：[l+1, r-1] = [1, 2] = "bb" 长度 = r - l - 1 = 4 - 0 - 1 = 3? 错！ 实际是 [1,3) = s[1] 和 s[2]，长度 = 2 注意：退出 while 时 l=-1, r=4 回文边界是 [l+1, r-1] = [0, 3]，长度 = 3? 不对 实际 l=0 时已经判断 s[0]!=s[3]，所以回文不包括 0 和 3 正确：[1, 3) 不包括 r

五、复杂度分析

最坏情况

字符串是全相同字符，如 “aaaaa…”：

• 奇数中心：每个扩展 O(n) 次
• 偶数中心：每个扩展 O(n) 次
• 总计 O(n^2)

六、动态规划解法（对比）

思路

定义dp[i][j]= s[i…j] 是否是回文串。

状态转移：

• dp[i][j] = (s[i] == s[j]) && dp[i+1][j-1]
• 即首尾相等，且中间也是回文

classSolution{public:stringlongestPalindrome(string s){intn=s.size();if(n<=1)returns;vector<vector<int>>dp(n,vector<int>(n,0));intstart=0,maxLen=1;// 所有单字符都是回文for(inti=0;i<n;i++)dp[i][i]=1;// 枚举长度for(intlen=2;len<=n;len++){for(inti=0;i+len<=n;i++){intj=i+len-1;if(s[i]==s[j]){if(len==2)dp[i][j]=1;// "aa" 这种elsedp[i][j]=dp[i+1][j-1];}if(dp[i][j]&&len>maxLen){start=i;maxLen=len;}}}returns.substr(start,maxLen);}};

两种方法对比

七、Manacher 算法（了解即可）

核心思想

O(n) 时间复杂度的算法，利用回文串的对称性避免重复计算。

// 伪代码，不完整实现stringmanacher(string s){// 1. 插入分隔符，使奇偶统一string t="#";for(charc:s){t+=c;t+="#";}// 2. 计算每个位置的回文半径vector<int>p(t.size(),0);intcenter=0,right=0;for(inti=0;i<t.size();i++){intmirror=2*center-i;if(i<right)p[i]=min(p[mirror],right-i);// 中心扩展while(i-p[i]>=0&&i+p[i]<t.size()&&t[i-p[i]]==t[i+p[i]]){p[i]++;}// 更新 center 和 rightif(i+p[i]>right){center=i;right=i+p[i];}}// 3. 找出最长回文// ...}

面试中如果能提到 Manacher，可以加分，但中心扩展已经足够。

面试追问 FAQ

相关题目

总结

中心扩展法是最直观、最实用的解法，面试中推荐使用。如果面试官问更优解，可以补充 Manacher 算法的思想。