题目

思路

一句话：回文是“关于中心对称”的字符串，枚举中心向两边扩，谁扩得最远谁就是最长回文子串。

先想最直白的：枚举所有子串的左右端点 (i, j)，再逐个字符验证是否回文。子串有 O(n²) 个，每个验证 O(n)，总时间 O(n³)。n 到 1000 时约 10⁹ 次操作，会超时。

关键观察：一个子串是不是回文，完全由它的中心决定。中心分两类：

• 奇数长度：中心落在某个字符上，如 "racecar" 的中心是 e。
• 偶数长度：中心落在两个字符之间，如 "bb" 的中心在两个 b 中间。

所以只需要枚举这 2n-1 个中心（n 个字符 + n-1 个空隙），从中心同时向左右扩：两侧字符相同就继续，不同就停。

为什么更省：每个中心的扩展是连续的一段匹配，一旦失配立刻停，内部不会重复验证；而且只需保存“当前最长”的起点与长度，不需要存下所有子串状态。与区间 DP（dp[i][j] 表示 s[i..j] 是否回文）相比，两者都是 O(n²) 时间，但 DP 要 O(n²) 空间存整张表，中心扩展只需 O(1) 空间，所以选它。

解法

维护 bestStart（当前最长回文的起点）和 bestLen（长度），从 0 / 1 起步，逐个中心扩展：

1. 枚举中心 i：奇数中心 (i, i)，偶数中心 (i, i+1)。
2. 扩展：只要 left >= 0、right < n 且 s[left] == s[right]，就 left--、right++。
3. 循环停止时，真正的回文区间是 (left+1, right-1)，长度 right - left - 1；比历史最长更长就更新。
4. 最后返回 s.substr(bestStart, bestLen)。

以 s = "abbc" 走一遍：

每个中心最多扩 O(n)，所以总共 O(n²)。

下图把上面 4 个步骤串成流程，并逐步演示：

C++

class Solution {
public:
 string longestPalindrome(string s) {
 int n = (int)s.size();
 int bestStart = 0, bestLen = 1;   // 至少一个字符，必是回文
 for (int i = 0; i < n; ++i) {
 expand(s, i, i, bestStart, bestLen);      // 奇数长度：中心是 s[i]
 expand(s, i, i + 1, bestStart, bestLen);  // 偶数长度：中心在 s[i] 与 s[i+1] 之间
 }
 return s.substr(bestStart, bestLen);
 }  private:
 void expand(const string& s, int left, int
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。