5-最长回文子串

//给你一个字符串 s，找到 s 中最长的 回文 子串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "babad"
//输出："bab"
//解释："aba" 同样是符合题意的答案。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出："bb"
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由数字和英文字母组成 
// 
//
// Related Topics 双指针 字符串 动态规划 Manacher 算法 👍 8143 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /**
     * 思路：中心枚举法 枚举 所有的中心节点，中心节点 包含 i 和 i + 1
     * 解答成功:
     *  执行耗时:16 ms,击败了65.97% 的Java用户
     *  内存消耗:45.5 MB,击败了54.18% 的Java用户
     *  空间复杂度： O(1)
     *  时间复杂度： O(N ^2)
     *
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        if(s == null || s.length() == 0) {
            return s;
        }
        int max = 0;
        int left = 0, right = 0;
        for(int i = 0; i < s.length(); i ++) {
            int [] tempArray = getMaxLongestPalindrome(s, i, i);
            if(tempArray[1] - tempArray[0] + 1 > max) {
                max = tempArray[1] - tempArray[0] + 1;
                right = tempArray[1];
                left = tempArray[0];
            }
            tempArray =  getMaxLongestPalindrome(s, i , i +1);
            if(tempArray[1] - tempArray[0] + 1 > max) {
                max = tempArray[1] - tempArray[0] + 1;
                right = tempArray[1];
                left = tempArray[0];
            }
        }
        return s.substring(left, right+1);
    }

    public int[] getMaxLongestPalindrome(String s , int left, int right) {
        while (left >=0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left --;
            right ++;

        }
        return new int[]{left + 1,right - 1};
//        if(left < 0 || right >= s.length() ) {
//            return int[]{left,right};
//        } else {
//
//        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)