5. 最长回文子串

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

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

 思路：

运用动态规划的思想，对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。

代码：

class Solution {
    public String longestPalindrome(String s) {
        int len = s.length();

        if(len < 2){
            return s;
        }

        int maxLen = 0;
        int l = 0;
        int r = 0;
        boolean dp[][] = new boolean[len][len];

        for(int i = 0;i < len;i ++){
            dp[i][i] = true;
        }

        char[] ch = s.toCharArray();

        for(int j = 1;j< len;j ++){
            for(int i = 0;i < j;i ++){
                if(ch[i] != ch[j]){
                    dp[i][j] = false;
                }else{
                    if(j - i < 3){
                        dp[i][j] = true;
                    }else{
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
                if(dp[i][j] && j - i + 1 > maxLen){
                    maxLen = j - i + 1;
                    l = i;
                    r = j;
                }
            }
        }
        return s.substring(l,r + 1);
    }
}