2.LeetCode#5 Longest Palindromic Substring

題目描述

求給定字符串的最長回文子串

動(dòng)態(tài)規(guī)劃求解

可以創(chuàng)建一個(gè)數(shù)組記錄由i開始到j(luò)的子串是否是回文子串
滿足關(guān)系：
dp[i][j] = true ((j - i <= 3 && S[i] == S[j]) || i == j)
dp[i][j] = dp[i+1][j - 1] and S[i] == S[j](j - i > 3)
現(xiàn)在我們可以判斷字符串任意兩個(gè)位置是否是回文串瞬女，在遍歷一遍找出最長的即可
代碼如下(借鑒)：

public static String longestPalindrome(String s) {
        if(s.length() == 0 || s == null){
            return s;
        }
        int len = s.length();
        int maxLen = 0;
        String res = null;

        boolean[][] dp = new boolean[len][len];
        for(int i = len - 1;i >= 0;i--){
            for(int j = i;j < len;j++){
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i+1][j-1] == true);//（1）當(dāng)前遍歷到的子串i~j是否是回文子串取決于i+1~j-1涮因，也就是i~j中間的子串是否是回文并且s[i]是否等于s[j]爹袁；（2）dp[i][j]是為true則意味著i~j是回文子串凿菩，則在下面判斷后對res進(jìn)行更新斑粱；如果為false，則該子串不是回文子串趴生，開始遍歷下一個(gè)子串杠河。

                if(dp[i][j] == true && (res == null || j - i + 1 > maxLen)){//如果該子串長度更長，則更新res
                    res = s.substring(i, j+1);
                    maxLen = res.length();
                }
            }
        }
        return res;

    }

• 時(shí)間復(fù)雜度：O(n^2)
• 空間復(fù)雜度：O(n^2)

采用從中心擴(kuò)散的方法

由于我們注意到回文串是中心對稱的傻咖，因此可以以每一個(gè)字符作為中心出發(fā)去找他的最長回文串朋魔，與上述動(dòng)態(tài)規(guī)劃的方法相比，此方法節(jié)省了空間卿操。
代碼如下：

public static String longestPalindrome(String s){

        int n = s.length();
        if(n <= 1) return s;
        String longest = "";
        String str;
        for(int i = 0; i < n - 1; i++){

            str = findPalindrome(s, i , i);
            if(str.length() > longest.length()){
                longest = str;
            }
            str = findPalindrome(s, i, i+1);
            if(str.length() > longest.length()){
                longest = str;
            }
        }
        return longest;
    }

    public static String findPalindrome(String s, int left, int right){

        int l = left;
        int r = right;
        int n = s.length();
        while(l >= 0 && r < n && s.charAt(l) == s.charAt(r)){
            l--;
            r++;
        }
        return s.substring(l + 1, r);
    }

• 時(shí)間復(fù)雜度：O(n^2)
• 空間復(fù)雜度：O(1)