题解 | #密码截取#一种动态规划思路
密码截取
https://www.nowcoder.com/practice/3cd4621963e8454594f00199f4536bb1
看到大家的代码感觉自己真的有点愣头用动态规划的方法，思路可能跟大家有点不同就想写出来和大家分享一下，抛砖引玉
算法流程概述
用dp数组来表示到第i个字符附近的最长回文串长度
将dp[i-1]作为第一个判断分支
当前一个只有1，也就是他自己作为最长回文串的时候会有两种情况
首先判断i-2和i是否是一样的，如果是一样的就代表这里会产生长度为3的最长回文串，形如ABA这种，AB的dp分别对应1 1，在到A的时候发现A 和A可以相等就产生了长度为3的回文串
如果不满足就继续判断i-1和i是否相同，相同就判断他是2，形如AA，不相同意味着i是一个孤立的字符只能是A
接下来当i-1大于1的时候
首先判断i和i-dp[i-1]-1是否相等， 如果相等dp[i] = i+2，形如ABBBA这种，当到第5个A的时候，前面的B是3，意味着前面3个是对称的，如果这三个左右两边的字符都相等，就意味着这个最长回文子串长度就直接加上旁边的2个变成了5。当然我们要确保i-dp[i-1]-1要大于零，否则就会导致出现数组越界。
如果i-dp[i-1]-1不等的时候就考虑第i个字符和前面dp[i-1]个字符全都相等，相等dp[i] = dp[i-1] + 1。之所以要全部相等，是因为前dp[i-1]个字符要求对称相等，再加上第i个字符以后也要求对称相等，这两个约束条件就使得第i个字符和前面dp[i-1]个字符都要相等才能满足条件。
如果两个情况都无法满足就只能说明他是孤立的字符dp[i] = 1
综上，只需要用一个循环就能找到dp数组中的最大值得到答案
参考代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.file.NotDirectoryException;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
int[] dp = new int[str.length()];
dp[0] = 1;
for(int i=1; i<str.length();i++){
if(dp[i-1] == 1){
if(i >= 2 && str.charAt(i-2) == str.charAt(i)){
dp[i] = 3;
} else{
if(str.charAt(i) == str.charAt(i-1)){
dp[i] = 2;
} else{
dp[i] = 1;
}
}
} else{
if(i-dp[i-1]-1 >= 0 && str.charAt(i) == str.charAt(i-dp[i-1]-1)){
dp[i] = dp[i-1]+ 2;
} else{
boolean index = true;
for(int j=i-dp[i-1]; j < i; j++){
if(str.charAt(j) != str.charAt(i)) {
index = false;
break;
}
}
if(index){
dp[i] = dp[i-1] + 1;
} else{
dp[i] = 1;
}
}
}
}
int max = 1;
for(int i=0; i<str.length(); i++){
if(max < dp[i]) {
max = dp[i];
}
}
System.out.println(max);
}
}
投递华为HUAWEI等公司10个岗位
曼迪匹艾公司福利 121人发布