(动态规划) LeetCode5. 最长回文子串

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

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

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

方法一：动态规划

var longestPalindrome = function(s) {
    let res = '';
    let n = s.length;
    let dp = Array.from(new Array(n),() => new Array(n).fill(0));
    for(let i = n - 1;i >= 0; i--){
        for(let j = i;j < n; j++){
            dp[i][j] = s[i] === s[j] && (j - i < 2 || dp[i + 1][j - 1]);
            if(dp[i][j] && j - i + 1 > res.length){
                res = s.substring(i, j + 1)
            }
        }
    }
    return res;
};

方法二：中心扩展算法

var longestPalindrome = function(s) {
    let res = '', start = 0, end = 0;
    let len = s.length;
    var getMax = function(i, j) {
        while(i >= 0 && j < len && s[i] === s[j]){
            i --;
            j ++;
        }
        return j - i - 1;
    }
    for(let i = 0;i < len; i++){
        let a = getMax(i, i);
        let b = getMax(i, i + 1);
        let max = Math.max(a, b);

        if(max > end - start){
            start = i - ((max - 1) >> 1);
            end = i + ((max) >> 1);
        }
    }
    return s.substring(start,end+1);
};