5. 最长回文子串
一句话套路枚举 2n-1 个中心向两边扩(奇偶都要)
题目描述
给你一个字符串 s,找到 s 中最长的 回文 子串。
示例 1:
输入:s = "babad" 输出:"bab" 解释:"aba" 同样是符合题意的答案。
示例 2:
输入:s = "cbbd" 输出:"bb"
提示:
1 <= s.length <= 1000s仅由数字和英文字母组成
思路
思路
解法 A(中心扩展,推荐):枚举 2n-1 个中心(n 个字符中心 + n-1 个间隙中心),向两边扩。时间 O(n^2)、空间 O(1),最好写。
「奇偶两类中心」是本题唯一容易漏的点。
解法 B(区间 DP)
dp[i][j] = s[i..j] 是否回文 = s[i]==s[j] && dp[i+1][j-1]。
遍历顺序
i 从大到小(因为依赖 i+1)。Q131 预处理回文表用的就是它。
解法 C(Manacher)
O(n),利用「已知回文的对称性」跳过重复扩展,面试基本不要求手写。
注意
答案不唯一时("babad" 的 "aba"/"bab")只要长度对即可,别在测试里写死。
对比
Q647 是「回文子串个数」(同样中心扩展,累加次数);
Q680 是「最多删一个字符」(双指针 + 失败时各试一侧)。
图解
字符串
aacabdkacaa(来自本仓库测试数据,下标从 0 开始)逐帧动画
1 / 3
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
namespace lc0005 {
class Solution {
public:
string longestPalindrome(const string& s) {
if (s.size() < 2) return s;
int bestStart = 0, bestLen = 1;
for (int c = 0; c < (int)s.size(); ++c) {
// 两类中心都要试:奇数(以字符为中心)、偶数(以间隙为中心)
for (int offset : {0, 1}) {
int i = c, j = c + offset;
while (i >= 0 && j < (int)s.size() && s[i] == s[j]) {
--i;
++j;
}
int len = j - i - 1; // 退出时 i、j 都多走了一步
if (len > bestLen) {
bestLen = len;
bestStart = i + 1;
}
}
}
return s.substr(bestStart, bestLen);
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
lc0005::Solution s;
string r1 = s.longestPalindrome("babad");
CHECK_TRUE(r1 == "aba" || r1 == "bab"); // 两个都是正确答案
CHECK_EQ(s.longestPalindrome("cbbd"), string("bb"));
CHECK_EQ(s.longestPalindrome("a"), string("a"));
CHECK_EQ(s.longestPalindrome("ac"), string("a")); // 长度 1,取先出现者
CHECK_EQ(s.longestPalindrome("aacabdkacaa"), string("aca"));
CHECK_EQ(s.longestPalindrome("ccc").size(), (size_t)3); // 全同
CHECK_EQ(s.longestPalindrome("").size(), (size_t)0);