当前位置：首页 > news >正文

5. 最长回文子串

news 2026/5/11 10:42:04

5. 最长回文子串

中等

提示

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

示例 1：

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

示例 2：

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

提示：

1 <= s.length <= 1000
s仅由数字和英文字母组成

📝 核心笔记：最长回文子串 (Center Expansion)

1. 核心思想 (一句话总结)

“投石问路：以每一个可能的中心点（单个字符或两个字符的间隙）为圆心，向两边同时扩散，直到碰到不一样的字符为止。”

回文特性：中心对称。
中心点：对于长度为的字符串，共有个中心（个单字符中心，个双字符间隙中心）。
策略：枚举所有中心，向外while循环扩散。

2. 算法流程 (Split Loop Strategy)

奇数回文 (Odd)：

- 枚举i从0到n-1。
- 初始中心l = i,r = i(比如 "aba" 的 'b')。

偶数回文 (Even)：

- 枚举i从0到n-2。
- 初始中心l = i,r = i + 1(比如 "abba" 的中间缝隙)。

扩散 (Expand)：

- while (l >= 0 && r < n && s[l] == s[r])：只要不越界且字符相等，就继续l--,r++。

记录 (Update)：

- 循环结束时，l和r刚好停在第一个不匹配（或越界）的位置。
- 真实长度：(r - 1) - (l + 1) + 1=r - l - 1。
- 更新ansLeft和ansRight。

🔍 代码回忆清单

// 题目：LC 5. Longest Palindromic Substring class Solution { public String longestPalindrome(String S) { char[] s = S.toCharArray(); // 转数组提速 int n = s.length; int ansLeft = 0; int ansRight = 0; // 记录最佳区间的左闭右开 [start, end) // 1. 情况一：奇数长度回文 (中心是 1 个字符) for (int i = 0; i < n; i++) { int l = i; int r = i; // 核心扩散逻辑 while (l >= 0 && r < n && s[l] == s[r]) { l--; r++; } // 循环结束时，l 和 r 都是"越界"或"不匹配"的位置 // 回文范围是 [l+1, r-1]，长度 = r - l - 1 if (r - l - 1 > ansRight - ansLeft) { ansLeft = l + 1; ansRight = r; // 这里存 r 刚好符合 substring 的左闭右开 } } // 2. 情况二：偶数长度回文 (中心是 2 个字符之间) for (int i = 0; i < n - 1; i++) { int l = i; int r = i + 1; // 区别仅在于初始 r 的位置 while (l >= 0 && r < n && s[l] == s[r]) { l--; r++; } if (r - l - 1 > ansRight - ansLeft) { ansLeft = l + 1; ansRight = r; } } return S.substring(ansLeft, ansRight); } }

⚡ 快速复习 CheckList (易错点)

[ ]为什么长度是r - l - 1？

- 假设回文是 "bab"，下标 1。扩散结束时l停在 -1 (越界)，r停在 3 (越界)。
- 直接相减3 - (-1) = 4是不对的。因为l和r多走了一步。
- 实际回文长度是(r-1) - (l+1) + 1，化简后就是r - l - 1。

[ ]代码可以合并吗？

- 可以。通常会提取一个expand(i, j)函数，分别调用expand(i, i)和expand(i, i+1)，避免代码重复。

[ ]时间复杂度？

- 。每个中心向外扩散最多步，共有个中心。
- 相比 DP ( 空间)，这种方法空间是，常数更小，实际运行非常快。

🖼️ 中文数字演练

S = "babad"

ansLeft=0,ansRight=0(初始长度0)

奇数扫描i=1('a'):

- 初始l=1, r=1。匹配 ('a'=='a')。
- 扩散l=0, r=2。匹配 ('b'=='b')。
- 扩散l=-1, r=3。越界，停止。
- 长度3 - (-1) - 1 = 3。
- 更新ansLeft=0,ansRight=3(即 "bab")。

奇数扫描i=2('b'):

- 初始l=2, r=2。匹配。
- 扩散l=1, r=3。'a' != 'a' ? 匹配 ('a'=='a')。
- 扩散l=0, r=4。'b' != 'd'。不匹配，停止。
- 长度4 - 0 - 1 = 3。
- 长度没超过之前的 3，不更新 (或者更新 "aba"，长度一样)。

偶数扫描:

- i=0('b', 'a'): 不匹配。
- ...后续无更长。

最终结果: "bab" (或 "aba")。

📝 核心笔记：最长回文子串 (Unified Center Expansion)

1. 核心思想 (一句话总结)

“万物皆中心：不管是字符还是间隙，我都给它一个编号i。通过除法把编号还原成左右指针，一次循环搞定所有奇偶情况。”

总中心数：长度为的字符串，有个中心点。
映射公式：

- l = i / 2
- r = (i + 1) / 2
- 当i是偶数时，l == r(指向同一个字符，奇回文)。
- 当i是奇数时，l + 1 == r(指向相邻字符，偶回文)。

2. 算法流程 (Unified Loop)

遍历 (Loop)：

- i从0遍历到2 * n - 2(共2n - 1次)。

定位 (Locate)：

- 计算初始扩散点：l和r。
- 例如i=0->0,0(char 0)；i=1->0,1(gap 0-1)；i=2->1,1(char 1)。

扩散 (Expand)：

- 标准中心扩散逻辑：while (s[l] == s[r])向两边炸开。

更新 (Update)：

- 计算长度r - l - 1。
- 如果比当前记录的长，更新ansLeft和ansRight。

🔍 代码回忆清单

// 题目：LC 5. Longest Palindromic Substring class Solution { public String longestPalindrome(String S) { char[] s = S.toCharArray(); int n = s.length; int ansLeft = 0; int ansRight = 0; // 1. 统一遍历所有的"中心点" // N 个字符 + (N-1) 个间隙 = 2N - 1 个中心 for (int i = 0; i < 2 * n - 1; i++) { // 2. 核心映射技巧 // 偶数 i (0, 2...): l = k, r = k (单字符中心) // 奇数 i (1, 3...): l = k, r = k+1 (间隙中心) int l = i / 2; int r = (i + 1) / 2; // 3. 尝试扩散 while (l >= 0 && r < n && s[l] == s[r]) { l--; r++; } // 4. 记录最大值 // 此时回文区间是 (l, r)，长度 r - l - 1 if (r - l - 1 > ansRight - ansLeft) { ansLeft = l + 1; ansRight = r; } } return S.substring(ansLeft, ansRight); } }