最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。
最长回文子串.

暴力解法

    /**
     * 暴力解法
     * @param s
     * @return
     */
    public static String longestPalindrome(String s) {
        if (s.length()<2){
            return s;
        }
        char[] chars = s.toCharArray();
        int maxLen = 1;
        int begin = 0;
        for (int i = 0; i < chars.length-1 ; i++) {
            for (int j = i+1; j < chars.length ; j++) {
                if (j-i+1>maxLen && validPalindromic(chars, i, j)){
                    maxLen = j-i+1;
                    begin = i;
                }
            }

        }

        return s.substring(begin,begin+maxLen);
    }
    static boolean  validPalindromic(char[] chars,int left, int right){
        while(left<=right){
            if (chars[left] != chars[right])
                return false;
            left++;
            right--;
        }
        return true;
    }

中心扩散解法

    /**
     * 中心扩散
     * 问题 考虑到了 左索引 和 长度 相加计算右索引时需要-1 但没考虑到subString的参数是左闭右开 粗心!!
     * @param s
     * @return
     */
    public static String longestPalindrome2(String s) {
        if (s.length() < 2){
            return s;
        }
        int maxLen = 1;
        int begin = 0;
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length-1; i++) {
        	// 获取以 i 为中心的最长字串的长度
            int oddLen = getCenterLength(chars,i,i);
            // 获取以(i,i+1)为中心的最长字串的长度
            int evenLen = -1;
            if (chars[i] == chars[i+1]){
                evenLen = getCenterLength(chars,i,i+1);
            }
            // 获取两者中大的那一个
            int curMax = Math.max(oddLen, evenLen);
            if (curMax>maxLen){
            // 通过计算获得开始坐标和长度
                maxLen = curMax;
                begin = i - (maxLen-1)/2;
            }
        }

        return s.substring(begin,begin+maxLen);
    }

    static int getCenterLength(char[] chars, int left, int right){
        while (left >= 0 && right<chars.length && chars[left] == chars[right]){
                left--;
                right++;
        return right-left-1;
    }