L2-008 最长对称子串(Java)
AI 摘要鱼粮不足,AI 今天先歇着 · 正文在下面
题目
对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。
输入格式:
输入在一行中给出长度不超过1000的非空字符串。
输出格式:
在一行中输出最长对称子串的长度。
输入样例:
sh
Is PAT&TAP symmetric?
输出样例:
sh
11
sh
代码长度限制 16 KB
时间限制 200 ms
内存限制 64 MB
解法
这里我们采用用动态规划的思想,把一个大问题分解成子问题,利用子问题求出最终解。
这里我采用了二维数组 dp[i][j] 来存储每一个范围的回文串长度,即子问题的解,从最小的子串开始不断判断更新最大长度。
比如,在计算 dp[i][j] 时,如果字符串下标 i 与 j 相等,则只需判断 子串 dp[i+1][j-1] 是否是回文串,无需重复计算,时间复杂度为。
代码实现:
java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
// L2-008 最长对称子串
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
int len = str.length();
if (len == 0) { // 如果字符串为空,则返回0
System.out.println(0);
return;
}
int[][] dp = new int[len][len]; // dp[i][j] 存储从 i 到 j 的最长回文子串的长度
int maxCount = 1; // 默认最长回文子串的长度为1
// 基本情况:单个字符是长度为 1 的回文串
for (int i = 0; i < len; i++) {
dp[i][i] = 1;
}
// Is PAT&TAP symmetric?
// s PAT&TAP s
// 遍历字符串以计算回文子串的长度
// 从回文串长度为2的字符串开始查询
for (int l = 2; l <= len; l++) {
for (int i = 0; i < len - l + 1; i++) {
int j = i + l - 1; // 当前子串的结束索引
// 当前串中长度范围的满足回文串两端相等
if (str.charAt(i) == str.charAt(j)) {
if (l == 2) {
// 长度为 2 的回文串
dp[i][j] = 2;
} else if (dp[i + 1][j - 1] > 0) {
// 如果内部子串是回文串,则当前回文串等于子串加两边字符
dp[i][j] = dp[i + 1][j - 1] + 2;
}
maxCount = Math.max(maxCount, dp[i][j]); // 如果找到更长的回文串,则更新 maxCount
}
}
}
System.out.println(maxCount);
}
}

评论
0 条—
还没有评论,来说第一句