问题描述

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

找出最长回文子字符串。

举个例子：

Example 1:
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:
Input: "cbbd"
Output: "bb"

类似题目：

[647] Palindromic Substrings{:target=”_blank”}

Update at 2020_0723

重新梳理下当头尾两个字符相等时的场景：

首先，判断它的左下角元素是否为0，如果是，

那么再去判断i + 1是否等于j，也就是aa这种情况，

如果i + 1 == j，则返回j - i + 1。

否则，返回0，没有找到回文子串，如: abca

否则，直接在bottomLeft的基础上加2即可，如：aba

来看下实现：

class Solution {
    public String longestPalindrome(String s) {

        int n = s.length();
        if (n == 0) return "";
        int[][] dp = new int[n][n];
        int max = 0, x = 0, y = 0;
        for (int i = n - 1; i >= 0; i--){
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++){
                if (s.charAt(i) == s.charAt(j)){
                    if (dp[i + 1][j - 1] == 0){
                        // eg: aa
                        if (j - i == 1)
                            dp[i][j] = j - i + 1;
                        // eg: abca
                        else
                            dp[i][j] = 0;
                    } else {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                    if (dp[i][j] > max){
                        max = dp[i][j];
                        x = i;
                        y = j;
                    }
                }
            }
        }
        return s.substring(x, y + 1);
    }
}