【动态规划-2】5.最长回文子串

题目描述：

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

如果字符串向前和向后读都相同，则它满足 回文性。

子字符串 是字符串中连续的 非空 字符序列。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

解题思路：

方法一：中心扩展法(最优解)

核心思路：

回文串一定有一个中心：

• 奇数长度：中心是一个字符（如 "aba" 中心是 b）

• 偶数长度：中心是两个字符之间（如 "abba" 中心是 bb 之间）

从每个中心向两边扩展，找到最长的回文。

具体过程示例：

s = "babad"

中心 i=0 ('b'): 扩展 → "b"
中心 i=1 ('a'): 扩展 → "bab"
中心 i=2 ('b'): 扩展 → "aba"
中心 i=3 ('a'): 扩展 → "a"
中心 i=4 ('d'): 扩展 → "d"

偶数中心:
中心 i=0.5: 扩展 → ""
中心 i=1.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[i+1] 之间
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; // 回文长度
}
};

复杂度分析

方法二：动态规划

思路：

dp[i][j] 表示 s[i..j] 是否是回文。

• s[i] == s[j] 且 dp[i+1][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;

vector<vector<bool>> dp(n, vector<bool>(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[i+1][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 # $

• ^ 和 $ 是哨兵，防止扩展时越界

• 它们不相等，扩展到这里一定停止

第二步：定义半径数组 p

p[i] 表示以 i 为中心的回文半径（包含中心）。

以 "#a#b#a#" 为例：

原串回文长度 = 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

遍历：

maxLen = 3, maxCenter = 4

start = (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();
vector<int> 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)？
因为 right 只增不减，每次扩展都会增加 right，总扩展次数不超过 n。

三种方法对比：

中心扩展是面试首选：代码简洁，空间 O(1)，时间复杂度 O(n²) 对大多数场景够用。

关键细节：

1. 为什么中心扩展要处理奇偶两种情况？

• 奇数回文："aba"，中心是单个字符

• 偶数回文："abba"，中心是两个字符之间

所以需要对每个位置调用两次扩展：expand(i, i) 和 expand(i, i+1)。

2. 为什么返回 right – left – 1？

循环结束时，left 和 right 已经越界或不匹配。回文长度 = (right – 1) – (left + 1) + 1 = right – left – 1。

3. 动态规划的遍历顺序

必须按长度递增遍历，因为 dp[i][j] 依赖 dp[i+1][j-1]（更短的子串）。

总结：