最长回文子字符串（中心拓展法）

package com.wzl.day16;

public class Day16 {
    //给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
//
// 示例 1：
//
// 输入: "babad"
//输出: "bab"
//注意: "aba" 也是一个有效答案。
//
//
// 示例 2：
//
// 输入: "cbbd"
//输出: "bb"
//
// Related Topics 字符串 动态规划


    //leetcode submit region begin(Prohibit modification and deletion)a
    public String longestPalindrome(String s) {
        if (null == s || s.length() <= 1) {
            return s;
        }

        // 记录回文子串的开始位置
        int start = 0;
        // 记录回文子串的结束位置
        int end = 0;

        for (int i = 0; i < s.length(); i++) {

            // 以每个字符为中心去扩展，例如"aba"就是以'b'为中心
            int len1 = expandAroundCenter(s, i, i);
            // 以两字母之间为中心去扩展，例如 "abba" 的中心在两个 'b'之间
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = Math.max(len1, len2);

            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }

        return s.substring(start, end + 1);
    }

    /**
     * 找到以left和right为中心的最大回文串长度
     *
     * @param s
     * @param left
     * @param right
     * @return
     */
    private int expandAroundCenter(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }

        return right - left - 1;
    }
//leetcode submit region end(Prohibit modification and deletion)

}