L2-008 最长对称子串(Java)

2024-03-25数据结构与算法2 分钟117 次阅读
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] 是否是回文串,无需重复计算,时间复杂度为O(n2){O(n^2)}。

代码实现:

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);
	}

}
image.png
觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句