LeetCode(5)：求出s中最長的回文子串

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

示例 1：

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

該題可用動态規劃，中心擴充，Manacher來解決

1.動态規劃

思路

右指針從第二位開始，左指針在右指針的位置前面進行順序檢測是否存在回文子串，檢測到滿足條件就在對應的數組标記為true，若滿足條件的子串長度比目前的最長長度長，就更新最長長度變量和最長的回文子串，左指針每周遊完一次，右指針就向右移動一次。

思想

對每個子問題（及子問題的子問題）隻求解一次，将其解儲存在一個表格中，進而在計算大規模的問題的時候，小規模的問題已經計算過，進而避免了不必要的計算工作。

複雜度

初始化二維數組時就已經把時間複雜度變成了O(n2)了（雖然這個算法本身複雜度就是O(n2)），我納悶的是為什麼java二維數組初始化時不能同時給每個值設定預設值呢，問題求解了好久也不知道該怎麼設定預設值，根據我記得的基礎，這是二維數組，二維數組裡的對象初始化都是null，隻能雙重循環加入數字就很難受了。

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if(len <= 1) return s;
        String maxStr = s.substring(0,1);
        Boolean[][] dp = new Boolean[len][len];
        for(int i = 0; i < len; i ++)
            for(int j = 0; j < len; j ++)
                dp[i][j] = false;

        int maxlen = 1;
        for(int r = 1; r < len; r ++){
            for(int l = 0; l < r; l ++){
                if(s.charAt(l)==s.charAt(r) && (r-l<=2 || dp[l+1][r-1])){
                    dp[l][r]=true;
                    if(r-l+1 > maxlen){
                        maxlen = r-l+1;
                        maxStr = s.substring(l, r+1);
                    }
                }
            }
        }
        return maxStr;
    }
}
           

中心擴充（待更）