HJ32 密码截取 | 题解
动态规划算法流程：
-
确定状态：对比的两个字符索引起始和终止索引位置
-
定义 dp 数组：字符串s的 i 到 j 索引位置的字符组成的子串是否为回文子串
-
状态转移: 如果左右两字符相等, 同时[j+1...i-1]范围内的字符是回文子串, 则 [j...i] 也是回文子串
-
状态转移的同时，不断更新对比的子串长度，最终确定最长回文子串的长度
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()) {
String str = in.nextLine();
int len = str.length();
boolean[][] dp = new boolean[len][len];
int res = 0;
for (int i = 0; i < len - 1; i++) {
dp[i][i] = true;
}
for (int i = 1; i < len; i++) {
for (int j = 0; j < i; j++) {
if (str.charAt(j) == str.charAt(i) && (j + 1 >= i - 1 || dp[j + 1][i - 1])) {
dp[j][i] = true;
res = Math.max(res, i - j + 1);
}
}
}
System.out.println(res);
}
}
}
查看21道真题和解析