【算法總結】字元串比對類型

最長回文子串

暴力法

時間複雜度： O ( N 3 ) O(N^{3}) O(N3)

空間複雜度： O ( 1 ) O(1) O(1)

• 根據回文子串的定義，枚舉所有長度大于等于2的字串，依次判斷它們是否為回文子串
• 可以隻針對大于目前得到的最長回文子串長度的子串進行回文驗證
• 當得到了一個更長的回文時，不需要真的做截取。隻需要記錄目前子串的起始位置和子串長度

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();
        if(len<2){
            return s;
        }  
        int maxLen = 1;
        int begin = 0;
        char[] charArray = s.toCharArray();
        // 枚舉所有長度大于1的子串,charArray[i...j]
        for(int i=0; i<len-1;i++){
            for(int j=i+1;j<len;j++){
                if(j-i+1 > maxLen && validPalindromic(charArray, i, j)){
                    maxLen = j-i+1;
                    begin = i;
                }
            }
        }
        return s.substring(begin, begin+maxLen);
    }
    /**
     * 驗證子串s[left...right] 是否為回文串
     */
    private boolean validPalindromic(char[] charArray, int left, int right){
        while(left < right){
            if(charArray[left] != charArray[right]){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}
           

動态規劃法

中心擴散法