题目描述:给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。回文是一个正读和反读都相同的字符串。
示例:输入: "babad" 输出: "bab"
Java代码:
class Solution {
//动态规划
public String longestPalindrome(String s) {
int n = s.length();
if(n < 2) return s;
if(n == 0 || s == null) return "";
int max = 1, begin = 0;
//matrix[i][j]表示s[i][j]是否是回文子串
boolean[][] matrix = new boolean[n][n];
char[] s_new = s.toCharArray(); //转换为数组可以避免使用s.charAt(i)操作增加算法运行时间
for(int i = 0;i < n;i++) matrix[i][i] = true; //对角线元素也就是子串长度为1时,一定是回文子串
for(int j = 1;j < n;j++) {
for(int i = 0;i < j;i++) {
//matrix[i][j] = s_new[i] == s_new[j] && (j - i < 3 || matrix[i + 1][j - 1])
//下面的逻辑可以简化为上面这一句话,但是没有铺垫不好理解
if(s_new[i] != s_new[j]) matrix[i][j] = false;
else {
if(j - i < 3) matrix[i][j] = true;
else matrix[i][j] = matrix[i + 1][j - 1];
}
//当matrix[i][j]为true时,就表示s[i...j]是回文子串,此时记录子串长度和起始位置
if(matrix[i][j] && j - i + 1 > max) {
max = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + max);
}
//暴力解法,时间复杂度为n的三次方
public String longestPalindrome2(String s) {
if(s == null || s.length() == 0) return "";
int n = s.length();
String max = "";
for(int i = 0;i < n;i++) {
for(int j = i;j < n;j++) {
if(isPalindrome(s.substring(i, j + 1)) && j - i + 1 > max.length())
max = s.substring(i, j + 1);
}
}
return max;
}
public boolean isPalindrome(String s) {
String d = new StringBuilder(s).reverse().toString();
return s.equals(d);
}
}
网友评论