题解 | #最长回文子串#

Leetcode大佬讲解的很好。这里记录下。两种方法：中心扩散和动态规划。
值得注意的是中心扩散在该题比动态规划好。

public int getLongestPalindrome(String A, int n) {
    // 中心扩散
    if(A == null || n <= 1) return n;
    int maxLen = 1, left = 0, right = 0, len = 0;
    for (int i = 0; i < n; i++) {
        left = i - 1;
        right = i + 1;
        while(left >= 0 && A.charAt(left) == A.charAt(i)){
            left--;
            len++;
        }
        while(right < n && A.charAt(right) == A.charAt(i)){
            right++;
            len++;
        }
        while(left>=0 && right < n && A.charAt(left) == A.charAt(right)){
            right++;
            left--;
            len += 2;
        }

        if(len > maxLen){
            maxLen = len;
        }
        len = 1;
    }
    return maxLen;
}

public int getLongestPalindrome(String A, int n) {
    // 动态规划
    if(A==null || n <= 1) return n;
    int maxLen = 1;
    boolean[][] dp = new boolean[n][n];
    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }
    for (int j = 1; j < n; j++) {
        for (int i = 0; i < j; i++) {
            if(A.charAt(i) == A.charAt(j)){
                if(j - i < 3){
                    dp[i][j] = true;
                }else{
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }

            if(dp[i][j] && j - i + 1 > maxLen){
                maxLen = j - i + 1;
            }
        }
    }
    return maxLen;
}