最长回文子串

[toc]

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

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

示例 2：

输入: "cbbd"
输出: "bb"

解题思路：

中心拓展法

image.png

进化未为麻辣车的形式：

马拉车的形式
会将原来的长度n，增加到2n+1
原来的位置为i，新的数组则为2i，反之依然。

长度问题 若是回文长度为3 实际上是1，所以为新数组的(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);
            // 当前的大于之前的
            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;
        
    }
}