题解 | #最长回文子串#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param A string字符串
     * @return int整型
     */
     /**
    思路：创建boolean 类型 二维dp[i][j] 表示从i到j是否是回文子串
                 从子串长度入手0 ~ n-1
                 然后遍历每一个起始 i 判断当前 i到j是否是回文子串
                 如果 子串长度为0 或者 1 则一定是
                 如果  子串长度 >1  则要判断 当前子串的子串dp[i+1][j-1] 是否是回文子串

      */
    public int getLongestPalindrome (String A) {
        // write code here

        int res = -1;

        int n = A.length();

        //dp[i][j] 表示从i到j 这个子串是否是回文串
        boolean [][]dp = new boolean[n][n];

        //子串长度 从1开始遍历到整个字符串的长度
        for (int c = 0 ; c < n ; c++) {
            for (int i = 0 ; i < n - c ; i++) {
                // i 是子串开始的下标
                // j 是子串结束的下标
                int j = i + c;
                if (A.charAt(i) == A.charAt(j)) {
                    //当当前子串长度为 0 或 1 时 代表只有一个字符 一定是回文串
                    if (c <= 1) {
                        dp[i][j] = true;
                    } else {
                        if (dp[i + 1][j - 1])
                            dp[i][j] = true;
                    }

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


            }
        }

        return res;


    }
}