0%

leetcode刷题记---最长回文子串

问题描述

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2:

输入: “cbbd”
输出: “bb”

题目出处:leetcode

题目分析

回文字符串,即正读和反读都相等的字符串,例如”aba, bb, aabbaa”都是回文字符串。

笔者作为一个算法菜鸡,第一眼看到这个题目首先想到的便是把输入字符串的所以子串遍历出来,然后挨个验证每个子串是否是回文字符串,从中找出最长的输出,并且题目描述中可以看出,如果存在多个最长子串,那么要求输出位置最靠近原字符串尾部的那一个。

暴力解题法

顺着最开始的思路来剖析一下我们需要干一些什么事情:

  1. 首先,需要遍历出所有的子串。因为需要找出最长的回文子串,那么先从最长的子串找起,这里需要一个循环遍历子串的长度length;(第一个循环)
  2. 然后,对于每个给予的长度length,再遍历出所有需要的子串;(第二个循环)
  3. 最后对于每个子串,再对其验证是否为回文子串;(第三个循环)

顺着这个思路,开始编码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
function longestPalindrome(s) {  
if (s.length <= 1) {
return s;
}

// 验证子串函数
function varifySubStr(subStr) {
let start = 0;
let end = subStr.length - 1;

while (start < end) {
if (subStr[start] !== subStr[end]) {
return false;
}

start++;
end--;
}

return true;
}

for(let length = s.length; length > 0; length--) {
// 第一个循环,从最长的长度开始遍历长度
let start = s.length - length;
let end = s.length - 1;

while(start >= 0) {
// 第二个循环,从原始字符串的尾部开始找出所有的子串
let substr = s.substring(start, end+1);

if (varifySubStr(substr)) {
// 如果找到了回文字符串,就立即返回
return substr;
}

end--;
start--;
}
}

return '';
};

以上的思路还是很简单的,但是时间复杂度着实高(O(n^3)),只能勉强通过leetcode测试。

暴力破解法:

  • 时间复杂度:O(n^3);
  • 空间复杂度: O(1);

优化思路

那么从暴力破解法开始看,这三个循环是否有可以优化的点呢?

  1. 已经验证过找到的子串能否重复利用以减少子串的多次遍历呢?
  2. 在验证子串的时候使用了一个循环,能否将这个循环和查找子串的过程的循环结合起来以减少复杂度呢?

动态规划法

先从第一个点入手,我们需要将已经判断过子串信息便能后续利用起来。那么应该如何利用呢?

在暴力破解法中的校验过程中,可以将已经判断过不符合条件的子串记录在一个varifyMap,即记录:

  1. 子串的中心点center;
  2. 上一次以这个中心收缩的不符合条件的右边界right;

并且当之后传入同样以center为中心的子串,如果该子串的边界大于等于上次不符合条件的边界记录,那么该子串一定不是回文子串。于是我们将代码更改如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
function longestPalindrome(s) {  
if (s.length <= 1) {
return s;
}

// 存储已经判断过的子串信息
let varifyMap = {};

// 验证子串函数
function varifySubStr(start, end) {
let center = (start + end) / 2;

if (varifyMap[center] && end >= varifyMap[center]) {
// 如果之前有相同中心的判断记录并且不符合条件的边界小于等于需要判断的子串,那么该子串一定不是回文子串
return false;
}

while (start < end) {
if (s[start] !== s[end]) {
// 将不符合条件的边界存储起来
varifyMap[center] = end;
return false;
}

start++;
end--;
}

return true;
}

for(let length = s.length; length > 1; length--) {
// 第一个循环,从最长的长度开始遍历长度
let start = s.length - length;
let end = s.length - 1;

while(start >= 0) {
// 第二个循环,从原始字符串的尾部开始找出所有的子串

if (varifySubStr(start, end)) {
// 如果找到了回文字符串,就立即返回
return s.substring(start, end+1);
}

end--;
start--;
}
}

return s[s.length - 1];
};

似乎感觉优化成功了,但是这里使用了更多的存储空间来存储之前的判断信息,即使减少的时间复杂度,但是增加了更多的空间复杂度。如果遇到特别长的并且最长回文子串很短的子串,这个算法反而会花费更多的计算时间。

优化结果(相较于暴力破解法):

  1. 时间复杂度 O(n^3) => O(n^2);
  2. 空间复杂度 O(1) => O(n^2);

中心扩展法

那么现在尝试第二种思路 => 将验证过程的循环和子串遍历的循环整合成一个。

经过上面的尝试,不难发现,确定一个回文子串有两种方法:

  • 找到子串的左右边界;
  • 找到子串的中心点和其中的一个边界点;

暴力破解法尝试的是第一种方法,那第二种方法是不是有奇效呢?那我们来试一下:

  1. 遍历原字符串的每一个点,以其为中心center;
  2. 以center向左右两侧展开,找到以center为中心点的最长的回文串;
  3. 在2的循环中,记录并比较回文串的长度,存储最长的回文子串并返回;

OK! Start coding!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function longestPalindrome (s) {
if (!s) {
return '';
}

// 以center为中心展开,查找最长的回文串
function findLongestResByCenter(s, left, right) {
let [l, r] = [left, right];
while (l >= 0 && r < s.length && s[l] == s[r]) {
l--;
r++;
}
return [l+1, r-1];
}

let [start, end] = [0, 0];

for (let center = 0; center < s.length; center++) {
// 遍历中心点center
let [l1, r1] = findLongestResByCenter(s, center, center);
let [l2, r2] = findLongestResByCenter(s, center, center + 1);
let [left, right] = r1 - l1 > r2 - l2 ? [l1, r1] : [l2, r2];
if (right - left > end - start) {
start = left;
end = right;
}
}

return s.substring(start, end+1);
};

在该算法中,外层遍历中心点有一个循环,内层查找并验证子串有一个循环,因此时间复杂度成功地降到了O(n^2),并且也未增加额外的存储空间。

暴力破解法 => 中心扩展法:

  • 时间复杂度: O(n^3) => O(n^2);

Manacher 算法

在中心扩展算法中还存在可以优化的点:

  • 是否可以解决回文串长度奇偶的问题,减少一轮循环;
  • 已经判断过的回文串是否可以利用起来;

于是,Manacher算法诞生了。

关于Manacher算法网上各种详细的解释已经很多,这里笔者就不再赘述,只是阐释一下笔者自己的理解。

首先,解决回文串长度奇偶的问题。对于任意一个字符串,在其中和首尾插入字符串中并不存在的一个字符,例如#,无论原字符串长度奇偶,变换后都是偶数,于是”dabbac” 变成了 “#d#a#b#b#a#c#”,”dababac” 变成了 “#d#a#b#a#b#a#c#”。变化后的字符串并不影响之前的回文子串分布,并且在该变换后的字符串中存在的回文字符串一定是奇数长度的,即为 “#c#b#b#c#” 或者 “#c#a#c#” 这种形式。

然后,我们考虑将回文串查找过程中已经验证过的子串利用起来:

  1. 首先假设在计算过程中已经找到一个目前标杆回文子串flagStr,它的中心在原字符串索引为center, 它的右边界在原字符串索引为right,每当新的扩展中心点i超过right时,更新centeri,更新right为以i中心的最长回文串的右边界;
  2. 对于标杆回文子串flagStr,在flagStr的左半径如果存在回文子串preStr,假设其中心为preCenter,那么在其右半径一定也存在一个以preCenterMirror为中心的回文子串preStrMirror, 其中 preCenterMirrorpreCenter 对于 center 的镜像点;
  3. 所以在center之后的点就可以省去重复遍历以preCenterMirror的为中心的回文串,假设preStr中心到边界的长度为R(即回文串的半径)。那么对于preCenterMirror的回文串,只需要:
    • 当 preCenterMirror + R > right,从right开始扩展回文串;
    • 当 preCenterMirror + R < right, 从 preCenterMirror + R 开始扩展回文串;

综上所述,我们需要在中心扩展法的基础上增加两个操作:

  • 在原字符串中各字符间即首尾插入’#’以使原字符串始终为偶数;
  • 用一个与原字符串同样长度的数组p记录各个字符点为中心点的最长回文串信息;
  • 存储目前最长回文串的中心点及右边界;

为了避免在转换后字符串计算中遍历越界,故在首尾加入不同的两个字符’$’ 和 ‘@’;

由于转换后的字符串是原字符串长度的两倍,最后找出的最长回文子串的中心索引maxCenter长度maxLen,转换为原字符串中,中心索引为Math.floor(maxCenter / 2),长度为maxLen / 2

根据以上思路,start coding:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function longestPalindrome (s) {    
let t = s.split('').join('#');
t = `$#${t}#@`;
let n = t.length;
// 数组p用来记录已经扩展成功的子串中心点以及半径,p[i] = R,i为中心点索引,R为回文串半径
let p = new Array(n).fill(0);
let [center, right] = [0, 0];
let maxLen = 0;
let maxCenter = 0;
for (let i = 1; i < n - 1; i++) {
if (right > i) {
// 如果目前扩展的中心点在目前已计算出的标杆回文子串之内,寻找以i为中心的最长回文串的起始半径
// 因为center始终小于等于i, 所以i一定是大于 2*right - center的,即如果 i < right, 那么 i 一定在目前标杆回文子串之内
p[i] = Math.min(right - i, p[2 * center - i]);
}

while (t[i + p[i] + 1] == t[i - p[i] - 1]) {
// 中心扩展法计算回文串半径
p[i]++;
}

if (i + p[i] > right) {
// 当新的回文串边界超过了目前的标杆回文子串边界,更新标杆回文子串信息
center = i;
right = i + p[i];
}

if (p[i] > maxLen) {
// 更新最长回文串的信息
maxLen = p[i];
maxCenter = i;
}

}

let start = parseInt((maxCenter - maxLen) / 2);
return s.substring(start, start + maxLen);
};

在Manacher算法中,我们使用了一个与原字符串两倍长度的数组存储回文子串信息,并以此减少了中心扩展半径的循环,优化结果(相较于中心扩展法):

  • 时间复杂度: O(n^2) => O(n);
  • 空间复杂度: O(1) => O(n);