最長回文子串（LeetCode）

         回文的最大特點就是中心對稱，根據這個特點，我們解決這個問題的中心思想就是檢測每個位置的左右兩側是不是對稱的，并且記錄最長的對稱字元數。

      但是這種思路隻适用與121這種模式，對于1221這種模式需要進行适當的處理。而我所知道的有兩種方法。

一：修改字元串将字元串：向兩個字元中間插入特定的字元如：‘.’。即121-->1.2.1 ,  1221-->1.2.2.1。全部變成奇數字元串。

二：在擴散檢測前先檢測是否有相同字元。

第一種的代碼如下：

class Solution {
     public static String longestPalindrome(String s) {
        if(s==null||s.length()<=1)return s;
        //向傳入的字元串添加強定字元‘.’
        s = join(s.toCharArray(),'.');
        char[] char_s = s.toCharArray();
        String longest = char_s[0]+"";
        for(int i = 1;i<char_s.length-1;i++){
            int b = 0;
            //向第i個字元的兩側檢測相同字元
            while(i-b>=0&&i+b<char_s.length&&char_s[i-b]==char_s[i+b]){
                b++;
            }
            
            if (longest.length()<=((b-1)*2+1)) {
                //排除'.1.'模式的影響
                if(longest.length()==((b-1)*2+1)&&char_s[i-b+1]=='.')continue;
                longest = s.substring(i-b+1,i+b);
            }
            
        }
        //移除字元串中插入的固定字元
        return  longest.replaceAll("\\.","");
    }
    //向傳入的字元串添加強定字元‘.’
    public static String join(char[] chars, char c ){
        StringBuffer sf = new StringBuffer();
        for(int i = 0;i<chars.length;i++){
            sf.append(chars[i]);
            if(i!=chars.length-1)sf.append(c);
        }
        return sf.toString();
    }
}
           

第二種方法：

class Solution {
     public static String longestPalindrome(String s) {
        if(s.length()<=1)return s;
        char[] char_s = s.toCharArray();
        int maxLength = 0;
        int a = 0;
        int b = 0;
        for(int i = 0;i<char_s.length;i++){
            int firstIndex = i;
            int lastIndex = i;
            
            while(lastIndex+1<char_s.length&&char_s[i]==char_s[lastIndex+1])lastIndex++;
            
            while((firstIndex-1)>=0&&(lastIndex+1)<char_s.length&&char_s[(firstIndex-1)]==char_s[(lastIndex+1)]){
                firstIndex--;
                lastIndex++;
            }
            if(maxLength<=lastIndex-firstIndex){
                maxLength =lastIndex-firstIndex; 
                a = firstIndex;
                b = lastIndex;
            }
        }
         
        return  s.substring(a,b+1);
    }
}
           

題目來源：leetcode