5.最长回文字串

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

示例 1：

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

示例 2：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1. 暴力求解法
   这种方法思路是 : 变量i从索引0开始遍历，变量j从索引i开始，i的边界范围为length，j的边界范围为length + 1 (因为slice方法是左开右闭的区间) ，这样就可以拿到字串(a,ab,abc,abcd...)，双重循环中通过isPalindromic方法判断是否为回文字串，最后更新最长字串的值，时间复杂度为，可以通过93个测试用例。

/**
 * @param {string} s
 * @return {string}
 */

var isPalindromic = (s)=> { 
    const len = s.length 
    for(let i=0;i<len/2;i++) { 
        if(s.substr(i,1) !== s.substr(len-1-i,1)) { 
            return false 
        }
    }
    return true 
}

var longestPalindrome = function(s) {
    let ans = '', // 记录值
    len = s.length, // 字符串长度
    max = 0;
    for(let i=0;i<len;i++) { 
        for(let j=i+1;j<=len;j++) {
            // 此时的子串可以这样获得
            let palinStr = s.slice(i,j)
            if(isPalindromic(palinStr) && palinStr.length > max ) { 
                // 记录回文字串的值 并更新max 
                ans = palinStr 
                max = palinStr.length
            }
        }
    }
    return ans
};

这是可以通过的方法，采用了动态规划的方法。主要思路是如果s[l,r]是一个回文字串，那么将它左右各减一个字符串s[l+1,r-1]也是一个回文字串。

var longestPalindrome = function(s) {
    const length = s.length 
    if(length<=1) return s ;
    const dp = [] 
    // 初始化二维数组
    for(let i=0;i<length;i++) { 
        dp[i] = []
        for(let j=0;j<length;j++) { 
            dp[i][j] = false 
        }
    }
    let max = 1,
        res = s[0]
    for(let r=1;r<length;r++) { 
        for(let l=0;l<r;l++) { 
             // 状态转移方程：如果头尾字符相等并且中间也是回文
             // 在头尾字符相等的前提下，如果收缩以后不构成区间（最多只有 1 个元素），直接返回 True 即可
             // 否则要继续看收缩以后的区间的回文性
             // 重点理解 or 的短路性质在这里的作用
            if(s[r] === s[l] && (dp[l + 1][r - 1] ||r-l<=2 ) ) { 
                dp[l][r] = true 
                let cur_len = r - l + 1
                 if( cur_len > max ) { 
                    max = cur_len
                    res = s.slice(l,r+1)
                 }
            }
        }
    }
    return res
};