5.最长回文子串.md

描述:

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

示例:

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

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

解析:

这个问题的解分成两种形式，第一种是常规解法，第二种是采用动态规划的方式来优化时间复杂度。 解法一: 回文子串长度分为偶数和奇数两种形式，循环遍历s的每个字符，记当前遍历节点为i，偶数情况下以i和i+1为起始点，向两边扩散查找最长回文子串，奇数情况以i-1和i+1为中心点扩散查找。更新每次遍历结果，返回结果值。 时间复杂度：O(n^2) / 空间复杂度：O(n)

解法二：构造一个二维数组dp，dp[i][j]表示字符串s第i位到第j位是否为回文串，初始化dp[i][i]为true。循环遍历s，将问题分解成求s子串长度从0到s.length的解，来构造dp数组。当s[i] === s[j]时，如果满足 i-j < 2则两元素相邻，为回文串，否则判断s串的j+1到i-1为是否为回文串，更新最长子串索引位置。 时间复杂度：O(n^2) / 空间复杂度：O(n^2)

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome_general = function(s) {
    let result = ''
    for(let i = 0; i < s.length; i++) {
        const str_even = generatePalindrome(i , i+1, s)
        const str_odd = generatePalindrome(i-1, i+1, s)
        const longest = str_even.length > str_odd.length ? str_even: str_odd
        if(result.length < longest.length) result = longest
    }
    return result

    function generatePalindrome(backward, forward, s) {
        while(forward < s.length && backward > -1) {
            if(s[forward] !== s[backward]) break
            forward += 1
            backward -= 1
        }
        return s.substring(backward + 1, forward)
    }
};

var longestPalindrome_dp = function(s) {
    const dp = new Array(s.length).fill(0).map(i=> [])
    let left = 0,
        right = 0,
        longest = 0
    for(let i=0; i<s.length; i++) {
        for(let j=0; j<i; j++) {
            dp[j][i] = (s[i] === s[j]) && ( i - j < 2 || dp[j+1][i-1])
            if( dp[j][i] && longest < i - j + 1) {
                longest = i - j + 1
                left = j
                right = i
            }
            dp[i][i] = 1
        }
    }
    return s.substring(left, right + 1)
};