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

示例 1：

輸入: "babad"
輸出: "bab"
注意: "aba" 也是一個有效答案执泰。
示例 2：

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

兩種解法：

    /**
     * 解法1：找到最長回文字符串，（dp渡蜻，從中間找术吝，往兩邊擴散计济，因為回文是對稱的）
     */
    public String longestPalindrome(String s) {
        int len = 0;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            int cur = Math.max(getLen(s, i, i),
                getLen(s, i, i + 1));
            if (cur > len) {
                len = cur;
                start = i - (cur - 1) / 2;
            }
        }
        return s.substring(start, start + len);
    }

    public int getLen(String s, int l, int r) {
        while (l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {
            --l;
            ++r;
        }
        return r - l - 1;
    }

    /**
     * 解法2：找到最長回文字符串，（最長公共子串排苍，dp）

      注意：  最長公共子串不一定就是回文哦
     */
    public String longestPalindrome2(String s) {
        if (s.equals("")) return s;
        String reverse = new StringBuilder(s).reverse().toString();
        int len = s.length();
        int[][] arr = new int[len][len];
        int maxLen = 0;
        int maxEnd = 0;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len; j++) {
                if (s.charAt(i) == reverse.charAt(j)) {
                    if (i == 0 || j == 0) {
                        arr[i][j] = 1;
                    } else {
                        arr[i][j] = arr[i - 1][j - 1] + 1;
                    }
                }
                if (arr[i][j] > maxLen) {
                    // 還需要判斷該字符串倒置前的下標和當前的字符串下標是不是匹配
                    int beforeRev = len - 1 - j;
                    if (beforeRev + arr[i][j] - 1 == i) {
                        maxLen = arr[i][j];
                        maxEnd = i;
                    }
                }
            }
        }
        return s.substring(maxEnd - maxLen + 1, maxEnd + 1);
    }

image.png

image.png