dp

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

示例 1：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

输入: "cbbd"
输出: "bb"

### 解题思路 思路就是当一个回文串左边和右边字符相等的时候可以扩展，但是栽在了好多特殊情况下，然后一一判断（菜鸡做法），还有一个超时了，a把print删了居然过了。

代码

class Solution {
    public String longestPalindrome(String s) {
        
        int left = 0;
        int right = 0;
        int l = s.length();
        if(l<2)return s;
        int[][] dp = new int[l][l];//dp[i][j]是i到j的子串是否是回文
        int i,j;
        for(i=0;i<l-1;i++){
            dp[i][i] = 1;//1代表是回文，长度为1当然是回文
            if(left == right){
                left = i;
                right = i+1;
            }
            for(j=i+1;j>0;--j){

                if(s.charAt(j-1) == s.charAt(i+1) && dp[j][i] == 1||s.charAt(j-1) == s.charAt(i+1)&&j>i){
                    dp[j-1][i+1]=1;
                    if((i-j+3)>=(right-left)){
                        left = j-1;
                        right = i+2;
                    }
                
                }
            }
        }
        return s.substring(left,right);
    }
}

Donate