type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
找字符串
s 中最长的回文子串。示例 1：
示例 2：
解法一：中心扩展（推荐）
以字符串中的每个位置（可以是单个字符，也可以是两个相邻字符之间的空隙）作为回文中心。
- 奇数回文中心在字符上（如
"aba"的b）；
- 偶数回文中心在两字符之间（如
"abba"的bb之间）。
从中心向两边同时扩展，尝试找到以该中心为对称轴的最长回文子串。
由于回文串的左右对称的特性，只要两边字符相等，就持续扩展，直到两边字符不相等或超出边界。
枚举所有可能的中心，分别计算其对应的最大回文长度，最长的那个子串作为答案。
复杂度
- 时间：
O(n^2)（中心数是2n-1，最坏扩展到两端）
- 空间：
O(1)
解法二：二维动态规划（区间 DP）
如果子串
s[i+1..j-1] 是回文，并且两头字符 s[i] == s[j]，那么把这两个相等的字符包上去，得到s[i..j] 也是回文。设
dp[i][j] 表示子串 s[i..j] 是否是回文。- Base Case：长度 1 的串天然是回文。
- 计算
dp[i][j]时用到dp[i+1][j-1]的结果，就必须从短到长地枚举区间。也就是算长度为L的区间，先要把长度为L-2的区间算完。
所以我们就从
L = 1 开始递增，枚举从索引i 开始的长度为 L 的子串 （ j = i + L - 1）。由于
dp[i+1][j-1] 的长度是 L-2，在计算长度为 L 的dp[i][j]之前已经先计算过了，可以直接用。复杂度
- 时间：
O(n^2)（所有区间各看一次）
- 空间：
O(n^2)（完整 DP 表）
解法三：一维动态规划
二维 DP在内存中有整个
n^2 的网格，实际上不是必需的。注意到 每次我们算一个值
dp[i][j] 时，都只需要 查看它斜对角的dp[i+1][j-1] 的值。任何时候，我们只需要缓存前一行的值。然后原地修改。
当固定
r=j 时，只需要用一维数组 dp[l] 表示 s[l..r] 是否回文。因为在二维 DP 中
dp[i][j] 依赖 dp[i+1][j-1] ， 所以让 i 从右往左扫（i = j, j-1, ..., 0）更新 dp[l]。再用一个变量
prev 暂存上一轮（r = j -1）的 dp[l+1]，这个值就是二维DP表里斜对角的 dp[l+1][r-1]。 这样只用 一行数组 + 一个常数变量
prev 就能表示二维 DP 表，从而把空间从 O(n^2) 降到 O(n)。复杂度
- 时间：
O(n^2)
- 空间：
O(n)（一行 DP数组）
解法四：Manacher （最优解）
- 先在字符串里插分隔符，比如
"abba"变成#a#b#b#a#。这样所有回文都变成“奇数长度”， 这样只需要维护一种情况。
- 在我们扫描到当前位置之前，所有已经找到的回文子串里，那个右端点最靠右的回文的中心是
center，右边界是right - 如果
i还在这段“最右回文”的覆盖里（i < right），那么i关于center的对称点mirror = 2*center - i的半径p[mirror]，可以直接给p[i]一个下界（最少这么长）。更具体地说，p[i]至少是min( right - i, p[mirror] )。 - 然后再在这个下界基础上，向外微调扩展（匹配不上才停）。
- 如果
i + p[i]超过了之前的right，那就更新“最右回文”的center = i、right = i + p[i]。 - 同时记录全局最大的
p[i]和它的中心，最终把答案从“带#的串”映射回原下标。
当我们来到新位置
i：这一步就像“白嫖”一段已经核实过的对称信息，不用从 0 开始扩。
复杂度
- 时间：
O(n)（右边界单调右移，总扩展次数线性）
- 空间：
O(n)（预处理后的字符串与半径数组）
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-5-最长回文子串
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 4] 两个排序数组的中位数
下一篇
[Leetcode 11] 盛最多水的容器