給定一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。你可以假設(shè) s 的最大長(zhǎng)度為 1000。

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個(gè)有效答案。

示例 2：

輸入: "cbbd"
輸出: "bb"

解題思路

遍歷字符串，分別以每個(gè)字符為中心向兩端擴(kuò)展，找到最長(zhǎng)的子串。

實(shí)現(xiàn)代碼

//執(zhí)行用時(shí) :28 ms, 在所有 Java 提交中擊敗了64.87%的用戶
//內(nèi)存消耗 :37.7 MB, 在所有 Java 提交中擊敗了72.98%的用戶
class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length(); i++) {
            int[] pair1 = expand(s, i, i);
            int[] pair2 = expand(s, i, i + 1);
            int len1 = pair1[1] - pair1[0] + 1;
            int len2 = pair2[1] - pair2[0] + 1;
            if (len1 > end - start + 1) {
                start = pair1[0];
                end = pair1[1];
            }
            if (len2 > end - start + 1) {
                start = pair2[0];
                end = pair2[1];
            }
        }
        
        return s.substring(start, end + 1);
    }
    
    public int[] expand(String s, int i, int j) {
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            --i;
            ++j;
        }
        return new int[]{i + 1, j - 1};
    }
}