(记录自己的leetcode之旅)
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
自己解法：
public static void main(String[] args){
System.out.println(longestPalindrome("abcdeaa"));
}
public static String longestPalindrome(String s) {
String result = "";
StringBuffer sb = new StringBuffer(s);
String str = sb.reverse().toString();
for(int i=0;i<s.length();i++) {
for(int j=i+1;j<=s.length();j++) {
if(str.indexOf(s.substring(i, j))>=0 && huiwen(s.substring(i, j))) {
result = s.substring(i, j).length()>result.length()?s.substring(i, j):result;
}
}
}
return result;
}
public static boolean huiwen(String s) {
if(s.length() == 1)
return true;
for(int i=0;i<s.length()/2;i++) {
if(s.charAt(i) != s.charAt(s.length()-i-1)) {
return false;
}
}
return true;
}
自己的解法还是暴力破解...超时了。
在网上找了找动态规划的做法。有的人贴出来的代码是不对的。接下来分析：
错误的动态规划解法：
i 是子串开头，j是子串结尾
状态初始条件：
dp[i][i]=1 （i=0：n-1）
状态转移方程：
dp[i][j]=dp[i+1][j-1] + 2 if（str[i]==str[j]）
dp[i][j]=max(dp[i+1][j],dp[i][j-1]) if （str[i]!=str[j]）
public int longestPalindrome(String str){
int n=str.length();
int dp[][] = new int[n][n];
for(int i=n-1;i>=0;i--){
dp[i][i]=1;
for(int j=i+1;j<n;j++){
if(str.charAt(i) == str.charAt(j)) {
dp[i][j]=dp[i+1][j-1]+2;
}
else
dp[i][j]=Math.max(dp[i+1][j],dp[i][j-1]);
}
}
return dp[0][n-1];
}
此状态转移方程放的最长回文子串的长度。看我来分析一下。
对于dp[i][i]=1，是指单个字符，单个字符必然是回文，长度是1。
对于dp[i][j]=dp[i+1][j-1] + 2 if（str[i]==str[j]），如果子串开头字符和结尾字符相等，那么从i-j的回文长度增加2.（!!!注意了，这里有错，因为它无法保证dp[i+1][j-1]的这个长度是回文的。举例：abcda，运行代码答案是3。显然不对，因为通过下个方程，bcd的回文串是1，所以答案是1+2=3。）
错误原因简单概括： abcda 字符串， bcd回文子串长度为1，abcda回文子串长度为1。但是根据以上方程 abcda回文子串长度为3。
正确的动态规划解法：
i 是子串开头，j是子串结尾
状态转移方程：
dp[i][j] = {true, i=j}
dp[i][j] = {str[i] == str[j] j-i=1}
dp[i][j] = str[i] == str[j] && dp[i+1][j-1] j-i>1}
public String longestPalindrome(String s) {
int n=s.length();
boolean dp[][] = new boolean[n][n];
int end=0;
int start=0;
for(int j=0;j<n;j++) {
for(int i=0;i<=j;i++) {
if(j-i<2)
dp[i][j]=(s.charAt(i)==s.charAt(j));
else{
dp[i][j]=(s.charAt(i)==s.charAt(j) && dp[i+1][j-1]);
}
if(dp[i][j] && end-start<(j-i)) {
start=i;
end=j;
}
}
}
return s.length()!=0?s.substring(start,end+1):"";
}
此状态转移方程放的true和false，即是否为回文串。
对于i=j的时候，单个字符，必为回文，所以dp[i][j]=true。
对于i+1=j的时候，两个字符，如果相同则为回文，所以dp[i][j]=(s.charAt(i)==s.charAt(j))。
对于i+1<j的时候，多个字符，在第i个字符等于第j个字符 并且 从i+1到j-1是回文子串的时候i-j才是回文子串，所以dp[i][j]=(s.charAt(i)==s.charAt(j) && dp[i+1][j-1])。
接下来得到回文子串还是算回文子串长度都OK了。
