经典问题-最长回文子串-DP

[liuyingbin19222]

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

示例二： 输入: "cbbd" 输出: "bb"

• 使用DP解法:

参考解法：https://blog.csdn.net/qq_31126175/article/details/84848290

var longestPalindrome = function(s){
    let len = s.length;
    let result;
    let i , j , L;
    let dp = Array(len).fill(0).map(x=>Array(len).fill(0));

    if(len <= 1){
        return s;
    }

    //只有一个字符的情况是回文;
    for(i = 0;i < len;i++){
        dp[i][i] = 1;
        result = s[i];
    }

    for(L = 2; L <= len; L++){
        for(i = 0;i <= len-L; i++){
            j = i + L - 1;
            if(L == 2 && s[i] == s[j]){
                dp[i][j] = 1;
                result = s.slice(i,i+L);
            }else if(s[i] == s[j] && dp[i+1][j-1] == 1){
                dp[i][j] = 1;
                result = s.slice(i,i+L);
            }
        }
    }
    return result;
}