力扣链接:5. 最长回文子串 - 力扣(Leetcode)

参考:

基础提升:3 KMP、Manacher算法等_哔哩哔哩_bilibili

算法学习笔记 | 62bit的秘密基地

解法一 中心扩散

以“122131121”为例,把每个字符当作一共回文串的中心,向两边扩散,记录最长的回文串的长度,但是这样会漏掉长度为偶数的回文串(例如1221),可以用特殊字符(例如 ’#‘)将每个字符分开,于是原始字符串变成了“#1#2#2#1#3#1#1#2#1#”,这样再用中心扩散法,然后把最后的答案除以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
33
34
35
36
37
38
class Solution {
public String longestPalindrome(String s) {
int n = s.length() * 2 + 1;
char[] newStr = new char[n];
int idx = 0;
for(int i = 0; i < n; i++){
if(i % 2 == 0){
newStr[i] = '#';//随便什么字符都可以,与原串里面的字符相同也行
}else{
newStr[i] = s.charAt(idx++);
}
}
int l = -1;//左指针
int r = -1;//右指针
int max = 1;//最大长度
int len = 1;//当前回文串的长度
int start = -1;//最大回文子串的起始位置
//遍历
for(int i = 1; i < n - 1; i++){
l = i - 1;
r = i + 1;
len = 1;
//扩散
while(l > -1 && r < n && newStr[l] == newStr[r]){
len += 2;
if(max < len){
start = l;
max = len;
}
l--;
r++;
}
}
if(start == -1) return s.substring(0, 1);
String res = new String(newStr).substring(start, start + max - 1);
return res.replaceAll("#","");
}
}

时间复杂度 O(n2),空间复杂度O(n)

解法二 Manacher

在解法一的基础上加了两个概念:

  1. 最大回文右边界:在扩散过程中,所有回文串能到达的最右边的位置
  2. 最大回文右边界对应的回文中心位置

优化策略:

  1. 情况一:当来到一个新的字符,它的位置(设为i)大于最大回文右边界,直接按照解法一来扩散

  2. 情况二:当来到一个新的字符,它的位置(设为i)小于等于最大回文右边界,一定会有以下位置关系:

    设最大回文右边界为R,其对应的中心位置为C,其关于C的对称位置为L,设i关于C的对称位置为 i’

    L i’ C i R

    其中 i 有可能与R重合

    此时以 i’ 为中心的回文串的范围有以下几种情况:

    1. i’ 的回文范围在L到R的范围内,此时i的回文范围大小与i’相同

      1
      2
      3
      for example: # a # b # c # b # d # k # s # k # d # b # c # b # a #
      ( i' ) ( i )
      L C R
    2. i’ 的回文范围左边界与L重合,此时i到R为半径的范围肯定是回文串,只需要从R+1的位置开始尝试向外扩

      1
      2
      3
      for example: # a # b # c # d # c # b # a # k # s # k # a # b # c # d # c # b # a #
      ( i' ) ( i )
      L C R
    3. i’ 的回文范围不全在L到R的范围内,此时i到R为半径的范围肯定是回文串,只需要从R+1的位置开始尝试向外扩

      1
      2
      3
      for example: # a # b # c # d # e # d # c # b # a # k # a # b # c # d # e # d # c # f # g
      ( i' ) ( i )
      L C R

    通过观察,情况二中的2和3情况相同

    于是可以写出以下伪代码:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    if(情况一){
    直接中心扩散
    }else{
    if(情况二中的1){
    i的回文半径 = i'的回文半径
    }else{//情况二中的2和3
    i的回文半径暂定为i到R
    尝试向外扩
    }
    }
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
52
53
54
55
56
57
58
59
60
class Solution {
public String longestPalindrome(String s) {
int n = s.length() * 2 + 1;
char[] newStr = new char[n];
int idx = 0;
for(int i = 0; i < n; i++){
if(i % 2 == 0){
newStr[i] = '#';
}else{
newStr[i] = s.charAt(idx++);
}
}
int R = -1;//最大回文右边界 + 1 的位置
int C = -1;//最大回文右边界对应的回文中心位置
int[] pArr = new int[n];//记录每个字符的回文半径
int max = -1;
int res = -1;
for(int i = 0; i < n; i++){
if(i > R - 1){//情况一:i 在最大回文右边界(R - 1)右边
pArr[i] = 1;//将回文半径暂定为1
while(i + pArr[i] < n && i - pArr[i] >= 0){//尝试往两边扩
if(newStr[i + pArr[i]] == newStr[i - pArr[i]]){
pArr[i]++;
}else{
break;
}
}
}else{//情况二:i <= 最大回文右边界(R - 1)
int i2 = 2 * C - i;//i'的位置
int i2Left = i2 - pArr[i2] + 1;//i'回文左边界
int L = C - pArr[C] + 1;//L
if(i2Left > L){// i'的回文范围在LR内部
pArr[i] = pArr[i2];//此时i的回文范围等于i'的回文范围
}else{// i'的回文左边界与L重合或者在L左边
pArr[i] = R - i;//i的回文范围暂定i到R
while(i + pArr[i] < n && i - pArr[i] >= 0){//尝试往两边扩
if(newStr[i + pArr[i]] == newStr[i - pArr[i]]){
pArr[i]++;
}else{
break;
}
}
}
}
//更新R和C
if(i + pArr[i] > R){
R = i + pArr[i];
C = i;
}
//记录最长回文子串的位置和半径
if(max < pArr[i]){
max = pArr[i];
res = i;
}
}
String ans = new String(newStr).substring(res - (max - 1), res + max);
return ans.replaceAll("#","");

}
}

再简化一下代码:

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
class Solution {
public String longestPalindrome(String s) {
int n = s.length() * 2 + 1;
int[] pArr = new int[n];//回文半径数组
char[] newStr = new char[n];
for(int i = 0; i < n; i++){
if(i % 2 == 0){
str[i] = '#';//随便选一个字符
} else {
str[i] = s.charAt(i / 2);
}
}
int R = -1;
int C = -1;
int max = -1;
int res = - 1;
for(int i = 0; i < n; i ++){
//i'的位置(2 * C - i)
//先判断i是否在LR之内(i > R - 1),
// 如果i在LR外,暂定i的回文半径为1
// 如果i在LR内
// 1. i'的范围在LR内:pArr[i] = pArr[2 * C - i]
// 2. i'的范围不全在LR内:pArr[i] = R - i
// 3. i'的范围左边界是L:pArr[i] = R - i
//以上浓缩成一行代码
pArr[i] = i > R - 1 ? 1 : Math.min(pArr[2 * C - i], R - i);
//pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
//判断能不能扩得更大
while(i + pArr[i] < n && i - pArr[i] >= 0){
if(newStr[i + pArr[i]] == newStr[i - pArr[i]]){
pArr[i]++;
}else{
break;
}
}
//更新R和C
if(i + pArr[i] > R){
R = i + pArr[i];
C = i;
}
//记录最长回文子串的位置和半径
if(max < pArr[i]){
max = pArr[i];
res = i;
}
}
String ans = new String(newStr).substring(res - (max - 1), res + max);
return ans.replaceAll("#","");
}
}

时间复杂度 O(n),空间复杂度O(n)

有点复杂,但仔细研究过觉得还好,不过感觉还是没有把Manacher写得很清楚啊。。