题目描述给你一个字符串s找到s中最长的回文子串。如果字符串向前和向后读都相同则它满足回文性。子字符串是字符串中连续的非空字符序列。示例 1输入s babad输出bab解释aba 同样是符合题意的答案。示例 2输入s cbbd输出bb解题思路方法一中心扩展法(最优解)核心思路回文串一定有一个中心奇数长度中心是一个字符如aba中心是b偶数长度中心是两个字符之间如abba中心是bb之间从每个中心向两边扩展找到最长的回文。具体过程示例s babad中心 i0 (b): 扩展 → b 中心 i1 (a): 扩展 → bab 中心 i2 (b): 扩展 → aba 中心 i3 (a): 扩展 → a 中心 i4 (d): 扩展 → d 偶数中心: 中心 i0.5: 扩展 → 中心 i1.5: 扩展 → ... 最长: bab 或 aba ✅代码实现class Solution { public: string longestPalindrome(string s) { if (s.empty()) return ; int start 0, maxLen 1; for (int i 0; i s.size(); i) { // 奇数长度回文中心是 s[i] int len1 expandAroundCenter(s, i, i); // 偶数长度回文中心是 s[i] 和 s[i1] 之间 int len2 expandAroundCenter(s, i, i 1); int len max(len1, len2); if (len maxLen) { maxLen len; start i - (len - 1) / 2; } } return s.substr(start, maxLen); } private: int expandAroundCenter(string s, int left, int right) { while (left 0 right s.size() s[left] s[right]) { left--; right; } return right - left - 1; // 回文长度 } };复杂度分析维度复杂度说明时间复杂度O(n²)每个中心扩展 O(n)共 n 个中心空间复杂度O(1)只用常数个变量方法二动态规划思路dp[i][j]表示s[i..j]是否是回文。s[i] s[j]且dp[i1][j-1]为真 →dp[i][j]为真边界j - i 1时只要s[i] s[j]就是回文代码实现class Solution { public: string longestPalindrome(string s) { int n s.size(); if (n 2) return s; vectorvectorbool dp(n, vectorbool(n, false)); int start 0, maxLen 1; // 初始化单个字符都是回文 for (int i 0; i n; i) { dp[i][i] true; } // 按长度递增遍历 for (int len 2; len n; len) { for (int i 0; i len - 1 n; i) { int j i len - 1; if (s[i] s[j]) { if (len 2 || dp[i1][j-1]) { dp[i][j] true; if (len maxLen) { maxLen len; start i; } } } } } return s.substr(start, maxLen); } };复杂度时间 O(n²)空间 O(n²)方法三Manacher 算法核心思路第一步预处理统一奇偶回文有两种奇数长度aba中心是单个字符偶数长度abba中心是两个字符之间Manacher 的做法是插入特殊字符把所有回文都变成奇数长度。插入#原串: a b a 新串: # a # b # a #原串: a b b a 新串: # a # b # b # a #效果原来奇数长度aba长度3→ 新串#a#b#a#长度7中心是b原来偶数长度abba长度4→ 新串#a#b#b#a#长度9中心是#所有回文都变成奇数长度中心唯一。再加两个哨兵新串: ^ # a # b # a # $^和$是哨兵防止扩展时越界它们不相等扩展到这里一定停止第二步定义半径数组pp[i]表示以i为中心的回文半径包含中心。以#a#b#a#为例i字符p[i]回文0#0#1a1#a#2#0#3b3#a#b#a#4#0#5a1#a#6#0#原串回文长度 p[i]因为插入#后半径正好等于原串回文长度。原串起始位置 (i - p[i]) / 2。第三步核心——利用对称性关键变量center当前最右回文的中心right当前最右回文的右边界center p[center]核心思想当遍历到i时如果i right说明i在某个回文内部。利用对称性i关于center的对称点是mirror 2 * center - i此时p[i]至少等于p[mirror]但有两种情况情况1: p[mirror] right - i → p[i] p[mirror]完全对称 情况2: p[mirror] right - i → p[i] right - i只能确定这么多需要继续扩展统一写法if (i right) { p[i] min(right - i, p[mirror]); }图解center ↓ ... [ ... i ... ] ... ↑ ↑ mirror right i 和 mirror 关于 center 对称第四步继续扩展确定p[i]的下界后继续向两边扩展while (t[i p[i] 1] t[i - p[i] - 1]) { p[i]; }因为加了哨兵^和$不会越界。第五步更新center和right如果i p[i] right说明找到了更靠右的回文更新if (i p[i] right) { center i; right i p[i]; }用例子走一遍s babad预处理t ^#b#a#b#a#d#$ 下标: 0 1 2 3 4 5 6 7 8 9 10 11 12遍历it[i]mirrorrightp[i]说明1#-00扩展失败2b-01#b#3#-00扩展失败4a-03#b#a#b#center4, right75#370irightp[5]min(2, p[3]0)06b271irightp[6]min(1, p[2]1)17#170iright扩展失败8a-71iright扩展#a#9#-7010d-71#d#maxLen 3, maxCenter 4start (4 - 3) / 2 0 结果 s.substr(0, 3) bab ✅代码实现class Solution { public: string longestPalindrome(string s) { // 预处理插入 # 变成奇数长度 string t ^#; for (char c : s) { t c; t #; } t $; int n t.size(); vectorint p(n, 0); int center 0, right 0; int maxLen 0, maxCenter 0; for (int i 1; i n - 1; i) { if (i right) { p[i] min(right - i, p[2 * center - i]); } while (t[i p[i] 1] t[i - p[i] - 1]) { p[i]; } if (i p[i] right) { center i; right i p[i]; } if (p[i] maxLen) { maxLen p[i]; maxCenter i; } } int start (maxCenter - maxLen) / 2; return s.substr(start, maxLen); } };复杂度分析维度复杂度说明时间复杂度O(n)每个字符最多被扩展一次空间复杂度O(n)p 数组 预处理字符串为什么是 O(n)因为right只增不减每次扩展都会增加right总扩展次数不超过 n。三种方法对比方法时间复杂度空间复杂度代码复杂度推荐度中心扩展O(n²)O(1)简单⭐⭐⭐⭐⭐动态规划O(n²)O(n²)中等⭐⭐⭐⭐ManacherO(n)O(n)复杂⭐⭐⭐中心扩展是面试首选代码简洁空间 O(1)时间复杂度 O(n²) 对大多数场景够用。关键细节1. 为什么中心扩展要处理奇偶两种情况奇数回文aba中心是单个字符偶数回文abba中心是两个字符之间所以需要对每个位置调用两次扩展expand(i, i)和expand(i, i1)。2. 为什么返回right - left - 1循环结束时left和right已经越界或不匹配。回文长度 (right - 1) - (left 1) 1 right - left - 1。3. 动态规划的遍历顺序必须按长度递增遍历因为dp[i][j]依赖dp[i1][j-1]更短的子串。总结要点说明核心思想从每个中心向两边扩展关键操作奇数中心(i,i)偶数中心(i,i1)时间复杂度O(n²)空间复杂度O(1)