题解 | #最长回文子串#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
     //dp[i][j] 表示以i-j的回文字符串
    public int getLongestPalindrome (String A) {
        // write code here
        int n = A.length();
        boolean[][] dp = new boolean[n][n];

        //1.初始化 虚拟节点为""

        //2.填表 1.i,j位置字符相同时，判断是该位置字符串长度如果i+1=j或者i=j，即为回文子串，如果i+1<j；说明长度大于2，此时就要判断dp[i+1][j-1]位置是否为回文子串
        int  max = 0;
        //此时我们填表顺序为从下到上，我们要根据dp[i+1][j-1]来判断
        for(int i=n-1;i>=0;i--){
            for(int j=i;j<n;j++){ 
                if(A.charAt(i)==A.charAt(j)){
                    dp[i][j] = i+1<j ?dp[i+1][j-1] : true;

                    if(dp[i][j]) max = Math.max(max,j-i+1);
                }
            }
           
        }

        return max;
    }

    

    
}