leetcode——5.最長回文子串

題目

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

示例 1：

輸入: “babad”

輸出: “bab”

注意: “aba” 也是一個有效答案。

示例 2：

輸入: “cbbd”

輸出: “bb”

思路

最簡單的方法，暴力破解，每一種情況都算一遍過去，循環時間複雜度為O(n^2)，驗證是否回文又需要O(n)的時間複雜度，妥妥的逾時，是以需要進行優化。

定義dp[i][j]表示從第i個字元到第j個字元是否為回文，則：

dp[i][j] = true i = j，即目前查找字元串長度為1時

dp[i][j] = s[i] == s[j] j-i = 1，即目前查找字元串長度為2時

若查找的字元串長度大于2時，隻需要知道i+1到j-1是否回文，是的話，則比較s[i],s[j]，不是的話，dp[i][j]也必定不為回文，即

dp[i][j] = dp[i+1][j-1] and s[i] == s[j]

動态規劃遞推式已求出，時間複雜度為O(n^2)，

空間複雜度為O(n^2)，空間複雜度上還可以繼續優化。

代碼如下：

class Solution {
    public String longestPalindrome(String str) {
        if(str.length() == 0){
            return "";
        }
        //最大起點和終點
        int maxS = 0,maxE = 0;
        int maxLen = 0;
    
        int len = str.length();
        boolean dp[][] = new boolean[len+1][len+1];
        for(int i = 1; i <= len; i++){
            for(int s = 0; s < len; s++){
                int e = s + i -1;
                //終點越界
                if(e >= len){
                    break;
                }
                if(i == 1){
                    dp[s][e] = true;
                }
                else if(i == 2){
                    dp[s][e] = str.charAt(s) == str.charAt(e);
                }else{
                    dp[s][e] = dp[s+1][e-1] && str.charAt(s) == str.charAt(e);
                }
                
                if(dp[s][e] && i > maxLen){
                    maxLen = i;
                    maxS = s;
                    maxE = e;
                }
            }
        }
        
        return str.substring(maxS,maxE+1);
    }

}
           

參考網上的代碼，此題還可以采用中心擴充的方法求解，大體思路為，標明一個中心點mid，向兩邊擴充，直到s[mid-1] != s[mid+1]，傳回長度。

中心點數量為2n-1, 若字元串長度為奇數，中心點隻有一個mid，此時中心點有n個，，若長度為偶數，則應該選取mid和mid+1為中心點，此時中心點有n-1個。

此種方法時間複雜度為O(n^2)，空間複雜度為O(1)，代碼就不貼了。

所講之處如有錯誤，還望指出，謝謝觀看。