最后编辑于2025-5-23
Medium
给定一个字符串 s，返回 s 中最长的回文子串。
示例 1：
输入： s = "babad"
输出： "bab"
解释： "aba" 也是可接受的答案。
示例 2：
输入： s = "cbbd"
输出： "bb"
约束：
1 <= s.length <= 1000 s 仅由数字和英文字母组成
问题分析与常用解法概览
回文串是正读反读都相同的字符串，如 "bob"、"level"、"noon" 等。求最长回文子串的常见方法包括：
- 中心扩展（Expand Around Center）——时间复杂度 O(n^2)，实现简单且常用。需同时处理奇偶长度回文。推荐在面试中先写这个并通过边界测试。
- 改进中心扩展的快速跳过重复字符方法——在遇到连续相同字符时先跳过以合并奇偶情形，能减少常数项操作。
- 动态规划（DP）——维护
dp[i][j] 表示子串 s[i..j] 是否为回文，时间与空间均为 O(n^2)，思路直观但空间开销大。
- 马拉车（Manacher）算法——将时间复杂度降到 O(n)，算法较巧妙但写起来相对复杂，适合追求最优时间的场景或刷题进阶。
下面给出四种实现（C++），并分别说明复杂度与要点。
方法一：中心扩展（基础版）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) return s;
int start = 0, maxLen = 1;
for (int i = 0; i < n; ++i) {
expandAroundCenter(s, i, i+1, start, maxLen);
expandAroundCenter(s, i, i, start, maxLen);
}
return s.substr(start, maxLen);
}
void expandAroundCenter(const string& s, int left, int right, int& start, int& maxLen) {
while (left >= 0 && right < (int)s.size() && s[left] == s[right]) {
--left; ++right;
}
int len = right - left - 1;
if (len > maxLen) {
maxLen = len;
start = left + 1;
}
}
};
|
- 时间复杂度： O(n^2)（最坏情况下每个中心扩展 O(n)）
- 空间复杂度： O(1)
方法二：中心扩展 + 跳过重复字符（优化常数项）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) return s;
int start = 0, maxLen = 1;
for (int i = 0; i < n;) {
if (n - i <= maxLen / 2) break;
int left = i, right = i;
while (right + 1 < n && s[right + 1] == s[right]) ++right;
i = right + 1;
while (left - 1 >= 0 && right + 1 < n && s[left - 1] == s[right + 1]) {
--left; ++right;
}
if (right - left + 1 > maxLen) {
maxLen = right - left + 1;
start = left;
}
}
return s.substr(start, maxLen);
}
};
|
- 时间复杂度： 仍为 O(n^2) 最坏，但常数项更小，实际更快。
- 空间复杂度： O(1)
方法三：动态规划（DP）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
string longestPalindrome(string s) {
if (s.empty()) return "";
int n = s.size();
vector<vector<bool>> dp(n, vector<bool>(n, false));
int left = 0, len = 1;
for (int i = 0; i < n; ++i) {
dp[i][i] = true;
for (int j = 0; j < i; ++j) {
dp[j][i] = (s[i] == s[j]) && (i - j < 2 || dp[j + 1][i - 1]);
if (dp[j][i] && i - j + 1 > len) {
len = i - j + 1;
left = j;
}
}
}
return s.substr(left, len);
}
};
|
- 时间复杂度： O(n^2)
- 空间复杂度： O(n^2)
备注： DP 直观但内存占用大，适合想要用状态定义来证明正确性的场景。
方法四：马拉车（Manacher）算法（O(n)）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
| class Solution {
public:
string longestPalindrome(string s) {
if (s.empty()) return "";
string t = "^#";
for (char c : s) { t += c; t += '#'; }
t += '$';
int n = t.size();
vector<int> p(n, 0);
int center = 0, right = 0;
int maxLen = 0, centerIndex = 0;
for (int i = 1; i < n - 1; ++i) {
int mirror = 2 * center - i;
if (i < right) p[i] = min(right - i, p[mirror]);
else p[i] = 0;
while (t[i + 1 + p[i]] == t[i - 1 - p[i]]) ++p[i];
if (i + p[i] > right) {
center = i;
right = i + p[i];
}
if (p[i] > maxLen) {
maxLen = p[i];
centerIndex = i;
}
}
int start = (centerIndex - maxLen) / 2;
return s.substr(start, maxLen);
}
};
|
- 时间复杂度： O(n)
- 空间复杂度： O(n)（用于转换后的字符串与半径数组）
要点： Manacher 在预处理后把奇偶回文统一成奇数情形，使用已知回文信息来跳过重复扩展，显著减少重复比较。
总结与建议
- 面试中优先写中心扩展解法（方法一或方法二），清晰易懂且能通过大多数测试；若需要更优的时间复杂度或想展示更高算法能力，再写 Manacher（方法四）。
- 动态规划适合证明和练手，但实现占用内存较大。
- 建议手写并调试中心扩展与 Manacher，熟悉两者的边界处理技巧（空串、全相同字符、偶数/奇数回文等）。
作者想说的话：
最长回文子串是字符串类题目的经典题型，理解“以中心扩展”与“预处理统一奇偶”的思想，会为你解其他字符串分割/匹配问题打下良好基础。
