【leetcode.5】最長回文子串

                                                最長回文子串

一、要求

給定一個字元串 s，找到 s 中最長的回文子串。你可以假設 s 的最大長度為1000。

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba"也是一個有效答案。      

示例 2：

輸入: "cbbd"
輸出: "bb"      

二、解法

這裡我們采用動态規劃。

主要思路：

（1）聲明一個布爾類型的二維數組dp，boolean[][] dp = new boolean[len][len]，len為字元串s的長度，那麼如果dp[i][j]為true時，則表示字元串s從第i個位置開始到第j個位置結束之間的子字元串為回文子串。

如：s="abac"，那麼此時dp聲明為dp[4][4]，那麼dp[0][0],dp[1][1],dp[2][2],dp[3][3],dp[0][2]都為true,表示對應位置的字母都是回文子串，那麼這裡最大長度的回文子串為aba。

（2）如果dp[i][j]為true，那麼dp[i+1][j-1]也必定為true，即“abba”為回文子串，那麼“bb”也為回文子串。是以我們的狀态轉移方程為dp[i+1][j-1]=true&&s.charAt(i)==s.charAt(j)  =>  dp[i][j]為true。

（3）如果j-i<=2時，即可能為回文的字元串最大長度為3時，如果有s.charAt(i)==s.charAt(j)，就直接斷定dp[i][j]=true，并不需要dp[i+1][j-1]=true。即當s="abad",i=0;j=2,s.charAt(0)==s.charAt(2)，則直接判定aba為回文字元串，即dp[0][2]=true。

（4）使用兩層for循環，外層循環訓示器i控制所求字元串的開始位置，内層循環訓示器j控制所求字元串的結束位置。但不是簡單的使得i從0開始，i++，j=i，j++，而是需要i從最大值開始，即字元串的長度-1開始，i--，j=i，j++，先求出小範圍内下标大的dp情況，再求出大範圍内下标小的情況，因為後者依賴前者。例如dp[0][3]依賴dp[1][2]的值。

三、代碼示範

public String longestPalindrome(String s) {
        if (s == null || s.equals("")) {
            return "";
        }
        int len = s.length();
        boolean[][] dp = new boolean[len][len];
        int maxLen = 0;
        int start = 0;
        int stop = 0;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if ((s.charAt(i) == s.charAt(j)) && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    if (maxLen < j - i + 1) {
                        maxLen = j - i + 1;
                        start = i;
                        stop = j;
                    }
                }
            }
        }
        return s.substring(start, stop + 1);
    }      

代碼送出結果：

四、複雜度分析

（1）時間複雜度