leetcode 5. 最长回文子串

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

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

/**
 * @param {string} s
 * @return {string}
 */
// 动态规划实现
var longestPalindrome = function(s) {
    let l = s.length;
    if(l<=1){
        return s
    }
    let ans = "";
    let dp = new Array(l).fill(0).map(()=>new Array(l));
    for(let i=1;i<l;i++){
        for(let j=0;j<=i;j++){
            // 满足以下条件，即相比较的两个字符相等且他们是同一个字符或相邻的字符或他们那各自往回缩一个字符还是回文
            if(s.charAt(i)===s.charAt(j)&&(i-j<2||dp[j+1][i-1])){
                dp[j][i]=true;
                let res =  s.substring(j,i+1);
                ans=res.length>ans.length?res:ans;
            }
        }
    }
    return ans;
};