题解 | #最长回文子串#

动态规划

O(N^2) O(N^2)

import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        // write code here
        // 状态定义：P(i,j)表示从i到j的子串是回文串
        // 状态转移：P(i,j)=P(i+1,j-1) and S[i] == S[j]
        // 边界条件：P(i,i)=true
        //         P(i,i+1) = (S[i] == S[i+1])
//         String res = "";
        int max_len = 0;
        boolean[][] dp = new boolean [n][n];
        for (int len = 0; len < n; len++){
            for (int i = 0; i+len < n; i++){
                int j = i + len;
                if (len == 0){
                    dp[i][j] = true;
                } else if (len == 1){
                    dp[i][j] = A.charAt(i) == A.charAt(j);
                } else {
                    dp[i][j] = A.charAt(i) == A.charAt(j) && dp[i+1][j-1];
                }

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

中心扩展

O(N^2) O(1)

import java.util.*;

public class Solution {
    public int getLongestPalindrome(String A, int n) {
        int max_len = 0;
        for ( int i = 0; i < A.length(); i++) {
            int len1 = getCenterAround(A, i, i); // 以i为中心向两边扩散
            int len2 = getCenterAround(A, i, i+1); // 以(i,i+1)为中心向两边扩散
            int len = Math.max(len1, len2);
            max_len = len > max_len ? len : max_len;
        }
        return max_len;        
    }
    private int getCenterAround(String A, int left, int right){
        while (left >=0 && right < A.length() && A.charAt(left) == A.charAt(right)) {
            left--;
            right++;
        }
        return right-left-1;
    }
}

如果要获取最长回文子串，可以得到该字串的左右下标，然后通过S.substring(i,j+1)来获得.
参考：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/