题解 | #密码截取#三种方法：暴力+dp+manacher
密码截取
https://www.nowcoder.com/practice/3cd4621963e8454594f00199f4536bb1
字符串中回文子串的最大长度
在字符串"12abba"中，最大的回文子串是"abba"，其长度为4.具体有以下三种方法：
方法一： 暴力解法
最简单的思路就是对字符串中每一个字符进行遍历，第一轮遍历每个位置，第二轮遍历以该位置展开的最大回文串。通过观察发现，除了有本例中的abba类型的偶数回文串，还有形如abcba的奇数回文串，因此在第二轮遍历时要分别考虑奇数和偶数两种情况，并更新记录最大值。
时间复杂度：O(N2) 空间复杂度：O(N)
private static int findLongetSub(String str) {
if(str == null || str.length() < 1) return 0;
char[] arr = str.toCharArray();
// 初始化最大值
int max = Integer.MIN_VALUE;
/**
* l,r -> 奇数情况左右边界
* dl,dr -> 偶数情况左右边界
*/
int l, r , dl, dr;
for (int i = 0; i < arr.length; i++) {
// 初始化左右边界 并找到左右边界极限值 要考虑边界条件
l = i; r= i;
while (l > -1 && r < arr.length && arr[l] == arr[r]){
l--;
r++;
}
if(i + 1 < arr.length && arr[i] == arr[i+1]){
dl = i;
dr = i + 1;
while (dl > -1 && dr < arr.length && arr[dl] == arr[dr]){
dl--;
dr++;
}
} else {
dl = i;
dr = i+2;
}
max = Math.max(max,Math.max(r-l-1,dr-dl-1));
}
return max;
}
方法二 ： 动态规划
对于字符str = 12abba，有20种子串，分别是1,12,12a,12ab,12abb,12abba,2a,2ab,2abb,2abba,a,ab,abb,abba,b,bb,bba,b,ba,a
可以建立一个二维数组，其中dp[i][j] = 以i为做边界，j为右边界的字符串的最大回文子串长度,限制 i > j时，dp[i][j]. = 0, i = j时，dp[i][j] = 1,
i < j 时，dp[i][j] = max(dp[i][j-1], dp[i+1][j])，当str[i] = str [j]时，若dp[i+1][j-1] = (i+1为左边界，j-1为右边界的字符串长度)，则dp[i][j] = (i为左边界，j为右边界的字符串长度) 否则还是dp[i][j]
dp[i][j]的更新规则为从左上到右下
时间复杂度：O(N2) 空间复杂度：O(N2)
private static int dp(String str) {
char[] arr = str.toCharArray();
int num = arr.length;
int[][] res = new int[num][num];
for (int i = 0; i < num; i++) {
res[i][i] = 1;
}
for (int i = 1; i < num; i++) {
for (int j = 0; j < num - i; j++) {
res[j][j+i] = Math.max(res[j+1][j+i],res[j][j+i-1]);
if(arr[j] == arr[j+i]){
res[j][j+i] = res[j+1][j+i-1] + 2 == i + 1 ? i + 1: res[j][j+i];
}
}
}
return res[0][num-1];
}
方法三： manacher算法
在进行Manacher算法时，字符串都会进行上面的进入一个字符处理，比如输入的字符为12abba，用“#”字符处理之后的新字符串就是#1#2#a#b#b#a#。
三个概念：
- 回文半径数组radius是用来记录以每个位置的字符为回文中心求出的回文半径长度
- 最右回文右边界r指的是这个位置及之前的位置的回文子串，所到达的最右边的地方
- 最右回文右边界的中心点C
具体可参考： Manacher算法的详细讲解
private static int manacher(String str) {
// 给str的每个字符间插上'#'
int l = str.length();
char[] arr = new char[l*2 + 1];
int[] radius = new int[l*2 + 1];
for (int i = 0; i < arr.length; i++) {
if(i % 2 == 0){
arr[i] = '#';
} else {
arr[i] = str.charAt((i-1)/2);
}
}
// 最右回文子串右边界
int r = -1;
// 最右回文子串对称中心
int c = -1;
int max = Integer.MIN_VALUE;
for (int i = 0; i < radius.length; i++) {
// 以i为中心点的回文字串半径最小由三方面决定
// 1。 当i<r，取i到r的距离与i以c为中心对称点的回文半径的最小值
// 2。 当i>=r,取1
radius[i] = i < r ? Math.min(r-i+1,radius[2*c-i]) : 1;
// 开始动态更新radius[i]
while (i + radius[i] < arr.length && i - radius[i] > -1){
if(arr[i + radius[i]] == arr[i - radius[i]]){
radius[i]++;
} else {
break;
}
}
// 动态更新r和c
if(i + radius[i] > r){
r = i + radius[i] - 1;
c = i;
}
max = Math.max(max, radius[i]);
}
return max - 1;
}
投递康冠科技KTC等公司10个岗位
我也是，前两面还挺紧张认真的，全程大脑飞速运转
后面就越来越不想面了，不想说话不想思考
查看10道真题和解析