首先说一下什么是回文串?
回文串就是一个字符串的逆序和正序相同,此字符串就是回文串。比如:abcdedc中的 cdedc就是会问串。那么回文串问题怎么解决呢?
前置操作:
因为回文串分为奇数串和偶数串,比如奇数串为:abcba这样是以c为中心向两边扩,直接遍历字符串就行了,但是如果遇到偶数串的时候直接遍历,判断两边字符是否相等就不行了,比如abba这样的字符,以两个b之间的位置作为中心,这样就需要添加辅助的字符,所以我们拿到字符串时,需要对字符串进行处理,把字符串的每个位置都插入其他字符,比如#a#b#b#a#这样我们直接遍历就行了,插入的辅助字符是否可以和已有字符相同呢?答案是:可以的,因为就算插入了辅助字符,还是已有字符和已有字符相比较,辅助字符和辅助字符相比较,所以是可以的。
方法一:朴素法
我们可以遍历每个字符串,然后向前向后分别扩充,最后得到最长的回文串。
时间复杂度为:O(n^2),空间复杂度为:O(1)代码实现如下:
public String longestPalindrome(String s) {
StringBuilder sb = new StringBuilder("#");
for (int i = 0; i < s.length(); i++) {
sb.append(s.charAt(i)).append("#");
}
char[] chars = sb.toString().toCharArray();
String maxStr = "";
int max = 0;
for (int i = 0; i < chars.length; i++) {
int j = 1;
while (i + j < chars.length && i - j >= 0 && chars[i - j] == chars[i + j]) {
j++;
}
if (max < j) {
max = j;
maxStr = sb.substring(i - j + 1,i + j);
}
}
return maxStr.replaceAll("#","");
}
方法二:Manacher算法
此方法的好处是时间复杂度可以接近O(n),通过维护一个半径数组,可以实现加速匹配字符串。有一个R为最右边界,维护匹配字符的最右边的字符。还有一个中心位置C位,这个的作用为可以快速找到回文串L-C-R之间的所有位置的半径。
主要分为四种情况:
- 右边界小于遍历的字符下标,则需要暴力匹配下一个字符,然后更新R。
- 匹配的字符小于右边界,并且C左边对应的半径也小于最左边界,则直接使用左边的半径。比如abcbdedbcbaerft,e中C位R为a,遍历到第二个c位置时就可以直接拿到第一个c的半径,因为其半径在最左边界内部。
- 匹配的字符小于右边界,但是C左边对应的半径大于左边界,则可以直接把半径写成R-i,因为如果R+1的字符等于L-1的字符的话,则还可以扩,之所以没有扩,就说明不等于。
- 匹配的字符小于右边界,但C左边对应的半径等于右边界,这种情况则需要暴力扩展了。可以直接扩展R+1位置。
代码实现如下:
public String longestPalindrome(String s) {
StringBuilder sb = new StringBuilder("#");
for (int i = 0; i < s.length(); i++) {
sb.append(s.charAt(i)).append("#");
}
char[] chars = sb.toString().toCharArray();
int[] ids = new int[chars.length]; // 回文半径数组
int C = -1; // 中心
int R = -1; // 最右边界,最右边有效区域为R-1
String maxStr = "";
int max = 0;
for (int i = 0; i < chars.length; i++) {
// ids数组加速i的匹配速度,如果之前匹配过了,则越过直接匹配没有匹配过的。
ids[i] = R > i ? Math.min(ids[2 * C - i],R - i) : 1;
// 暴力匹配按字符匹配。
while (ids[i] + i < chars.length && i - ids[i] > -1) {
if (chars[ids[i] + i] == chars[i - ids[i]]) {
ids[i]++;
} else {
break;
}
}
// 如果遍历字符超过最右边界,则更新最右边界,及中心位置
if (R < i) {
R = i + ids[i];
C = i;
}
if (max < ids[i]) {
max = ids[i];
maxStr = sb.substring(i - ids[i] + 1,i + ids[i]);
}
}
return maxStr.replaceAll("#","");
}
通过这个半径数组可以解决很多字符串的相似问题,半径数组是Manacher算法的核心。