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

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](https://my.oschina.net/u/2303379) s
 * [@param](https://my.oschina.net/u/2303379) left
 * [@param](https://my.oschina.net/u/2303379) right
 * [@return](https://my.oschina.net/u/556800)
 */
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)

}