[toc]

題目

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

示例 1：

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

示例 2：

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

解題思路：

中心拓展法

image.png

進(jìn)化未為麻辣車的形式：

馬拉車的形式
會將原來的長度n，增加到2n+1
原來的位置為i，新的數(shù)組則為2i，反之依然。

長度問題 若是回文長度為3 實(shí)際上是1，所以為新數(shù)組的(len-1)/ 2

class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return  "";
        }
       
        
        StringBuffer sb = new StringBuffer();
        for(int i =0; i<s.length(); i++) {
            sb.append("#");
            sb.append(s.charAt(i));
        }
         sb.append("#");
        
        char[] chars = sb.toString().toCharArray();
        
        int maxLen = 0;
        int start = 0;
        
        
        for(int i=1; i < chars.length-1; i++) {
            int len = getMaxLen(chars, i);
            // 當(dāng)前的大于之前的
            if(len > maxLen) {
                maxLen = len;
                // 別加太多 容易超過去
                start = i + 1 - maxLen;
            } 
          
        }
        
        return s.substring((start + 1) / 2,(start + 1) / 2 + maxLen -1);
        
    }
    
    /**
    * index為中心位置
    **/
    private int getMaxLen(char[] chars, int index) {
        
        int len = 0;
        while(len <= index && len < chars.length-index ) {
            if(chars[index+len] == chars[index- len ]) {
                len++;
            } else {
                return len;
            }
        }
        return len;
        
    }
}