LeetCode刷题【5】最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

动态规划

看一看，想一想，这题踩得坑比较多。

• 构建一个`N x N`的DP矩阵，
• 首先在所有`dp[i][i]`格子上表示可以构成回文子串，毕竟单自己一个字符是可以算的（如图）

• 构成回文有两种情况，一种是偶数长度的，中间两位是一样的，另一种是奇数长度的，中间单独一个前段和后段是一样的
• 与之对应的两种初始情况：AA型长度为2的两个相同字符，或者ABA型长度为3的收尾相同的3个字符
• 那么其他的情况当大于3的时候，假设字符串长度是k，且收尾字符串相同，则只需要判断中间的下标1到下标k-2是回文字符串就行

如图，我们从较小的范围，最底部开始

1. `dp[4][5]`位置对应结束字符横行的`b`和开始字符竖列的`b`两个字符相同，则判断此时距离为1，那么此时构成回文子串
2. 继续往上直到`dp[2][4]`位置，首位相等都是`b`，且距离大于1，则判断中间部分是否为回文子串，中间部分只有一个`c`是回文子串，那么`dp[2][4]`是回文子串
3. 继续往上到`dp[1][2]`，首位都是`b`且距离为1，是回文子串
4. 到`dp[1][5]`首位都是b，且距离大于1，判断中间的`dp[2][4]`是否是回文子串，`dp[2][4]`是回文子串，呢么对应的`dp[1][5]`也是回文子串
5. 后面就基本一样了，不用过多重复
6. 在每次判断得到结果为是回文子串的时候，根据开始结束位置我们能得到一个长度，把这个长度记下来，并每次比较取较大的一个长度和对应的左边起始位置。
7. 根据最终最大值的左起始位置和长度，构建返回新字符串。

class Solution {
    public String longestPalindrome(String s) {

        if (s.length()<=1){
            return s;
        }
        int l = s.length()-1;
        int r = 0;
        int maxLength = 1;
        int maxL = 0;
        boolean[][]dp = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
        while (--l >= 0){
            r = l;
            while (++r < s.length()){
                if (s.charAt(l)==s.charAt(r)){
                    if ( r==l+1){
                        dp[l][r] = dp[l + 1][r];
                    }else{
                        dp[l][r] = dp[l + 1][r - 1];
                    }
                }
                if (dp[l][r]){
                    if (maxLength < r-l+1){
                        maxL = l;
                        maxLength = r-l+1;
                    }
                }
            }
        }


        char[] arr = new char[maxLength];
        System.arraycopy(s.toCharArray(),maxL,arr,0,maxLength);
        return new String(arr);
    }
}