leetcode题目5：最长回文子串（java）

题目描述

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

示例

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

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

解题思路

1. 遍历字符串，以每个字符为中心展开，向左右两侧寻找回文串。再以两个字符之间为中心展开，向左右两侧寻找回文串。

代码

public String longestPalindrome(String s) {
    if (s == null || s.length() <= 0) {
        return null;
    }
    int start = 0;
    int end  = 0;
    int maxLength = 0;
    for (int i = 0; i < s.length(); i++) {
        int length1 = expandCenter(s, i, i);
        int length2 = expandCenter(s, i, i + 1);
        if (maxLength < Math.max(length1, length1)) {
            maxLength = Math.max(length1, length1);
            start = i - (maxLength - 1) / 2;
            end = i + maxLength / 2;
        }
    }
    return s.substring(start, end + 1);
}

private int expandCenter(String s, int left, int right) {
    while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
        left--;
        right++;
    }
    return right - left - 1;
}