2019-07-18 leetcode longestPali

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: "babad"

输出: "bab"

注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"

输出: "bb"

使用动态规划法：

避免在验证回文时进行不必要的重复计算。考虑 “ababa” 这个示例。如果我们已经知道 “bab” 是回文，那么很明显，“ababa” 一定是回文，因为它的左首字母和右尾字母是相同的。

P(i,j)=(P(i+1,j−1) and S​i​​==S​j​​)

我们首先初始化一字母和二字母的回文，然后找到所有三字母回文，并依此类推…

class LongestPalindrome{

    public static void main(String[] args) {

        System.out.println("babad: " + longestPalindrome("babad"));

        System.out.println("cbbd: " + longestPalindrome("cbbd"));

    }

    public static String longestPalindrome(String s) {

        if(s.length() < 2){

            return s;

        }

        boolean[][] dp = new boolean[s.length()][s.length()];

        String result = s.substring(0,1);

        for(int j = 0 ; j < s.length(); j++){

            for(int i = 0 ; i < s.length(); i++){

                dp[i][j] = (s.charAt(i) == s.charAt(j)) && (j - i <=2 || dp[i+1][j-1]);

                if(dp[i][j]){

                    if(j - i + 1 > result.length()){

                        result = s.substring(i,j+1);

                    }

                }

            }

        }

        return result;

    }

}