写一个用动态规划求最长回文子串的java函数
时间: 2024-03-13 18:27:58 浏览: 60
用动态规划思想求解最长公共子串
4星 · 用户满意度95%
public static String longestPalindrome(String s) {
if (s == null || s.length() < 2) {
return s;
}
int n = s.length();
int maxLen = 1;
int start = 0;
boolean[][] dp = new boolean[n][n];
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
for (int j = 1; j < n; j++) {
for (int i = 0; i < j; i++) {
if (s.charAt(i) == s.charAt(j)) {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
} else {
dp[i][j] = false;
}
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
start = i;
}
}
}
return s.substring(start, start + maxLen);
}
阅读全文