给定一个字符串
s
,找到s
中最长的回文子串。你可以假设s
的最大长度为 1000。
示例:
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 输入: "cbbd" 输出: "bb"
一开始我的思路是,先假设整个字符串就是回文,从两头往中间检查,如果两头已经不匹配,那假设字符串长度 – 1 的子字符串是回文,此时这样的子字符串有俩。依旧两头往中间检查,如果找不到,子字符串的长度减 1。如果子字符串长度为原字符串长度 – n,那么这样的子字符串有 n + 1 个,一直找直到找出来回文为止。
我本来觉得这样的做法应当比暴力法还是要快很多的,但实际上运行的得分不怎么样。这里我也就略过这种算法的代码了。
后来我看了看官方答案,看起来最有效率的方法应该是 Manache 法(中文叫『马拉车』,快被笑死……)。算法的重点都在理解思路,我自己对 Manache 的思路理解如下。
还是用一个最简单的例子来说明,给出这样一个字符串 AAABAAC
。
因为字符串回文长度为奇数和偶数时处理方式有点不同,为了统一处理,可以在字符串里面添加分隔符 |
来方便处理:|A|A|A|B|A|A|C|
。
接下来记录每个字符为中心时的回文长度数:
|A|A|A|B|A|A|C| 01 R
当我们遇到 A
时,出现了第一个回文,长度为 1(镜像部分长度而不是全部,后面一样),并且回文右边的 |
(标记了 R
)是目前发现出现回文最右边的边界。记录这些值的目的是什么呢?目前还看不出什么作用,但请先记住这个 R 的含义:出现回文时的最右位置。我们继续往下扫描:
|A|A|A|B|A|A|C| 012 R
当我们遇到第二个 |
时,出现了更长的回文,同时 R 也扩展到了更右,再往下看的时候,我们就能发现 R 的妙用了。
目前我们统计到每个位置的回文长度数,都是自己对比出来的,但实际上,由于回文自己本身的特点,如果 R 已经是字符串的最右边界,那回文中心 A
后面的数我们都不用统计了,因为它们也应该是对称的,我们可以管回文中心叫做『镜』:
|A|A|A|B|A|A|C| 0121 R
但 R 并不是『最右』,如果回文后面有某个字符,它的镜像回文统计长度,加上它自己本身的位置已经等于 R 这个位置了,那么我们可以尝试将 R 往右再推进试试,比如上面第二个 A
,即可以将 R 往后推一格,此时镜也变成了第二个 A
:
|A|A|A|B|A|A|C| 0123 R
我们继续往下统计。第三个 |
相对于新的镜的『像』,统计的结果为 2,但实际上第三个 |
的位置往后移动 2,又再 R 上,所以 R 是否还能往后推,是还需要验证的,但我们只需要从 R 的位置开始往后校验即可:
|A|A|A|B|A|A|C| 01232 R
结果发现 R 并没有往后推进。我们继续往下检查。实际上,我们最关心的事情,就是 R 能不能再往后推进:
|A|A|A|B|A|A|C| 01232105 R
遇到 B
之后,R 被大大往后推进了,镜也变成了 B
,我们按照上面的方法,继续往下检查,接下来要检查的 |
的『镜像』,回文长度为 0,本身往后移动 0 个位置不会超过 R,所以它的回文长度肯定是 0;再接下来的 A
,『镜像』回文长度是 1,但它本身往后 1 个位置也没超过 R,同理它的回文长度就是 1
|A|A|A|B|A|A|C| 0123210501 R
接下来的 |
我们得到镜像回文长度为 2,它往后移动 2 个位置正好是 R,所以我们尝试把 R 往后推,结果是没有推动,所以它的回文长度还是 2。
我们可以继续利用马拉车尝试将 R 拉更远,这里有一个聊胜于无的小优化,目前回文最长到 5,实际上从刚刚统计过的 |
开始,它到字符串结束正好是 5,所以可以直接停止统计了。
我们再回过头来看看整个过程,可以发现,Manache 算法充分利用了回文的特点,一个长度为 n 的字符串,平均每个字符实际只对比了一次,所以它的复杂度为 O(n)。
说完了思路,再来看看边界条件。假设我们要检查的点是 i
- 如果 i 正好踩在 R 这个位置,甚至超过 R,那显然要尝试将 R 推远
- 如果 i 的位置往后移动它镜像 i0 的最大回文数已经大于 R,则 i 的最大回文数应当是 R 到 i 的距离,并且也需要将 R 推远
- 如果 i 的位置往后移动它镜像 i0 的最大回文数不大于 R,则 i 的最大回文数跟 i0 位置是一样的,R 也不需要推进
综合上面的所有分析,代码如下
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
let a = [0, 1];
let m = 1;
let r = 2;
let i = 1;
let max = 1;
let imax = 1;
let len2 = s.length * 2 + 1;
while (i < len2 - 1) {
++i;
if (i + max > len2) {
break;
}
if (i < r) {
j = m + m - i;
if (i + a[j] < r) {
a[i] = a[j];
continue;
}
}
const d = Math.max(r - i + 1, 1);
let il = i - d;
let ir = i + d;
while (ir < len2 && il >= 0) {
if (il % 2 && s[(il - 1) / 2] !== s[(ir - 1) / 2]) {
break;
}
r = ir;
m = i;
++ir;
--il;
}
a[i] = r - i;
if (max < a[i]) {
max = a[i];
imax = i;
}
}
return s.substr(((imax - a[imax]) / 2) | 0, max);
};
本来是写的 PHP 版本,遗憾的是,LeetCode 不知为何,PHP 代码无法通过测试,但实际上,即使是在 LeetCode 自己的测试功能里试运行,报错的示例也是能通过的为了通过测试,我换成了 JavaScript 版本。
后来我发现原来跟使用了 static 关键字有关,修改之后 PHP 版也可以运行。
class Solution {
/**
* @param String $s
* @return String
*/
function longestPalindrome($s) {
$len = strlen($s);
if ($len < 2) {
return $s;
}
$a = [0, 1];
$m = 1;
$r = 2;
$i = 1;
$max = 1;
$imax = 1;
$len2 = $len * 2 + 1;
while ($i < $len2 - 1) {
++$i;
if ($i < $r) {
$j = $m + $m - $i;
if ($i + $a[$j] < $r) {
$a[$i] = $a[$j];
continue;
}
}
$d = max($r - $i + 1, 1);
$il = $i - $d;
$ir = $i + $d;
while ($ir < $len2 && $il >= 0) {
if ($il % 2 && $s[($il - 1) / 2] !== $s[($ir - 1) / 2]) {
break;
}
$r = $ir;
$m = $i;
++$ir;
--$il;
}
$a[$i] = $r - $i;
if ($max < $a[$i]) {
$max = $a[$i];
$imax = $i;
}
}
return substr($s, intval(($imax - $a[$imax]) / 2), $max);
}
}
再说说关于其他解法的理解。
动态规划
动态规划的核心是:将一个大问题,分解成更好思考的若干小问题。以最长回文为例,判断一个子字符串(假设为给定字符串的位置 i 到 j)是不是回文,可以分拆为判断从位置 i + 1 到 j – 1 是不是回文,以及 i 和 j 上的字符是否相同共同判断;可能大家已经看出来问题的拆分也成了一个套娃问题,最终会让 i 和 j 变成同一个位置,或者 i 和 j 相邻,此时问题就不能再拆了。另外为了提高运行速度,可以通过空间换时间的方式,将判断过的结果记录下来,形成一张表,因为当 i 和 j 相等的时候,一定是回文,对于一个总长度为 3 的字符串,表可以先这么初始化:
0 | 1 | 2 | |
0 | true | ||
1 | true | ||
2 | true |
对于 ABB
这个字符串,按照刚才所说的做法,最终会行成下面这张表:
0 – A | 1 – B | 2 – B | |
0 – A | 1. true | 2. false | 3. false |
1 – B | 1. true | 2. true | |
2 – B | 1. true |
进行到第二轮,也就是子字符为两个长度时,发现当 i 为 1, j 为 2 时,有最长的回文;进行到第三轮时,发现无法再找到回文,程序结束。
事实上,就算字符总长度再长一点,如果在之前的某一轮已经无法找到回文,按我们上面对回文问题的拆分,后面的轮次都没有必要进行了。
中心扩展
这个方法我觉得可能没有必要再多解释,因为 Manache 方法就是一个优化后的中心扩展方法。
LeetCode 刷题之最长回文 by Chris Yue is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

写作累,服务器还越来越贵
求分担,祝愿好人一生平安
天使打赏人