Problems->005.最长回文子串

(记录自己的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了。