用java实现:给你一个字符串 s,找到 s 中最长的回文子串。 如果字符串的反序与原始字符串相同,则该字符串称为回文字符串
时间: 2023-02-25 09:01:06 浏览: 111
如何求字符串里的最长回文子串
5星 · 资源好评率100%
可以使用动态规划来实现,具体可以参考下面的代码:public class Palindrome {
public static String longestPalindromeSubstring(String s) {
int n = s.length();
boolean[][] dp = new boolean[n][n];
int maxLength = 1;
int start = 0;
// 将二维数组的左上角全部赋值为true
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// 将二维数组的对角线全部赋值为true
for (int i = 0; i < n - 1; i++) {
if (s.charAt(i) == s.charAt(i + 1)) {
dp[i][i + 1] = true;
maxLength = 2;
start = i;
}
}
// 处理长度大于2的子串
for (int k = 3; k <= n; k++) {
for (int i = 0; i < n - k + 1; i++) {
int j = i + k - 1;
if (dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j)) {
dp[i][j] = true;
if (k > maxLength) {
maxLength = k;
start = i;
}
}
}
}
// 返回最长回文子串
return s.substring(start, start + maxLength);
}
}
阅读全文