LeetCode解題筆記 3 —— 5.最長回文子串

tips:回文的意思是正着念和倒着念一樣，如：上海自來水來自海上

問題

給定一個字元串 

s

，找到 

s

 中最長的回文子串。你可以假設 

s

 的最大長度為 1000。

示例 1：

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

示例 2：

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

解法

暴力解法：

class Solution {
    public String longestPalindrome(String s) {
        int length = s.length();
        if(s.length() < 2){
            return s;
        }
        int left=0; //目前最長回文子串的左下标
        int right=0;//目前最長回文子串的右下标
        int max = 1;//目前最長回文子串的長度
        for(int i = 0 ; i < length; i++){
            String str = s.substring(i,length);
            int l2 = str.length();
            if(l2<=max) break; //剩餘長度小于目前最長回文子串的長度，結束校驗
            for(int j = 0; j < l2; j++){
                if(j + 1<=max) continue;
                String msg = str.substring(0,j+1);
                boolean flag = true;//是否為回文字元串辨別
                int l3 = msg.length();
                int size = l3/2;
                for(int k = 0; k < size; k++){
                    if(msg.charAt(k)!=msg.charAt(l3-1-k)){
                        flag = false;
                        break;
                    }
                }
                if(flag){
                    if(l3>max){
                        max = l3;
                        left = i ;
                        right = i + j;
                    }
                }
            }
        }
        return s.substring(left, right + 1);
    }
}
           

将所有可能截取到的字元串都判斷一下是否為回文字元串，并選出最長的一種，這種解法結果雖然是正确的，但運作時間過長，占用記憶體過多，在LeetCode送出時有機率提示逾時，故需進行優化

優化解法：

class Solution {
    public String longestPalindrome(String s) {
        int length = s.length();
        if(s.length() < 2){
            return s;
        }
        int left=0; //目前最長回文子串的左下标
        int right=0;//目前最長回文子串的右下标
        int max = 1;//目前最長回文子串的長度
        
        
        int indexL,indexR;//中間部分字母連續相同的左右下标
        
        for(int i=0; i < length; i++){
            char c = s.charAt(i);
            indexL = i;
            indexR = i;
            //先擷取連續相同字元的左下标
            for(int k = 1; k <= i; k++){
                if(s.charAt(i-k)!=c){
                    indexL = i - k + 1;
                    break;
                }else if(k == i){
                    indexL = i - k;
                }
            }
            //擷取連續相同字元的右下标
            for(int k = 1; k <= length - 1 - i; k++){
                if(s.charAt(i+k)!=c){
                    indexR = i + k - 1;
                    break;
                }else if(k == length - 1 - i){
                    indexR = i + k;
                }
            }
            int z = indexR - indexL + 1;
            if(z>max){
                max = z;
                left = indexL;
                right = indexR;
            }
            //然後依次判斷左右兩邊的字元是否相同，直到出現不同或超出範圍為止
            for(int k = 1; k <= indexL; k++){
                if(indexL- k<0 || indexR+k>=length) break;
                char leftC = s.charAt(indexL- k);
                char rightC = s.charAt(indexR + k);
                if(leftC!=rightC){
                    int t = indexR + k - 1 - (indexL - k + 1) + 1;
                    if(max < t){
                        max = t;
                        left = indexL - k + 1;
                        right = indexR + k - 1;
                    }
                    break;
                }else if(indexL - k == 0 || indexR + k == length-1){
                    int t = indexR + k - (indexL - k) + 1;
                    if(max < t){
                        max = t;
                        left = indexL - k;
                        right = indexR + k;
                    }
                    break;
                }
            }
        }
        return s.substring(left, right + 1);
    }
}
           

優化後效果