力扣链接: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
在解法一的基础上加了两个概念:
- 最大回文右边界:在扩散过程中,所有回文串能到达的最右边的位置
- 最大回文右边界对应的回文中心位置
优化策略:
情况一:当来到一个新的字符,它的位置(设为i)大于最大回文右边界,直接按照解法一来扩散
情况二:当来到一个新的字符,它的位置(设为i)小于等于最大回文右边界,一定会有以下位置关系:
设最大回文右边界为R,其对应的中心位置为C,其关于C的对称位置为L,设i关于C的对称位置为 i’
L i’ C i R
其中 i 有可能与R重合
此时以 i’ 为中心的回文串的范围有以下几种情况:
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
|
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
|
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; 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){ pArr[i] = 1; while(i + pArr[i] < n && i - pArr[i] >= 0){ if(newStr[i + pArr[i]] == newStr[i - pArr[i]]){ pArr[i]++; }else{ break; } } }else{ int i2 = 2 * C - i; int i2Left = i2 - pArr[i2] + 1; int L = C - pArr[C] + 1; if(i2Left > L){ pArr[i] = pArr[i2]; }else{ pArr[i] = R - i; while(i + pArr[i] < n && i - pArr[i] >= 0){ if(newStr[i + pArr[i]] == newStr[i - pArr[i]]){ pArr[i]++; }else{ break; } } } } 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 ++){ pArr[i] = i > R - 1 ? 1 : Math.min(pArr[2 * C - i], R - i); while(i + pArr[i] < n && i - pArr[i] >= 0){ if(newStr[i + pArr[i]] == newStr[i - pArr[i]]){ pArr[i]++; }else{ break; } } 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写得很清楚啊。。