题目
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
1
2
3
| 输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
|
示例 2：
动态规划解法
以动态规划的思想，首要找到两个重要的点，一个是边界条件，一个是状态转移方程
本题目中，我们以dp[i][j]表示从i到j的字符串，s[i]或s[j]表示i或者j处的字符。
1
2
3
4
5
6
7
8
9
10
| dp[i][i] = 1
dp[i][i + 1] = {
1, s[i] == s[i + 1]
0, s[i] != s[i + 1]
}
dp[i][j] = {
dp[i + 1][j - 1], s[i] == s[j]
0, s[i] != s[j]
}
|
以上，可以看出当字符串长度大于等于2时，可以直接套用动态规划公式，于是有
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
| function solution(s){
const length = s.length;
if(length <= 1){
return s;
}
let dp = new Array(length).fill(0).map(x => new Array(length).fill(0));
let result = s.slice(0, 1);
for(let i = 0;i < length;i++){
dp[i][i] = 1;
}
for(let l = 2;l <= length;l++){
for(let i = 0;i <= length - l;i++){
let j = i + l - 1;
if(l == 2 && s[i] === s[j]){
dp[i][j] = 1;
result = s.slice(i, i + l);
}else if(l > 2 && s[i] === s[j] && dp[i + 1][j - 1]){
dp[i][j] = 1;
result = s.slice(i, i + l);
}
}
}
return result;
}
|
以上，就是最长回文子串的动态规划解法
Manacher（么那车）解法
这个解法的解释是，首先不管奇数长度还是偶数长度的统统转换成奇数长度，方法是在每个字符的左右两边各添加一个特殊字符，例如#；然后将扩展后的字符串从第一位开始，依次计算以当前位置C为中心点折叠字符串后，最大的重叠半径，这个思想可以类比为我们将一本打开的书合上的过程，只是两边的书页并不一定是完全对称的，那么书页合上后重合的部分就是我们想要的。
例如s = ‘abbc’， 扩展字符串为#a#b#b#c#；
从第一个#开始，以此#为中心点，折叠字符串，发现只有它本身和自己重叠，# => #，于是C0 = 1；
移动指针指向字符a，以a为中心点，折叠字符串，发现 #a# => a#，于是 C1 = 2；
再次移动指针指向字符#，以#为中心点，折叠字符串，发现 # => #，于是 C2 = 1；
再次移动指针指向字符b，以b为中心点，折叠字符串，发现 #b# => #b，于是 C3 = 2；
再次移动指针指向字符#，以#为中心点，折叠字符串，发现 #b#b# => #b#，于是 C4 = 3；
不断重复此过程直到字符串遍历完，得到maxC = C4 = 3，我们在此过程中记录最大值出现的数据，便可得到最长回文子串为#b#b#，去除#号后，得到bb。
Talk is cheap, show me ur code.
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
| function solution(s){
if(s.length <= 1){
return s;
}
let str = '#' + s.split('').join('#') + '#';
let maxR = 0;
let result = '';
for(let center = 0, R = 0;center < str.length; center++){
let flag = true;
R = 0;
while(flag){
let i = center - R, j = center + R;
if(i >= 0 && j < str.length && str[i] === str[j]){
R++;
}else{
flag = false;
if(maxR < R - 1){
maxR = R - 1;
result = str.slice(center - maxR, center + maxR + 1);
}
}
}
}
return result.split('#').join('');
}
|
以上，就是Manacher算法的具体实现。
