5. 最长回文子串

[wengzc]

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

示例 1：

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

示例 2：

输入: "cbbd"
输出: "bb"
通过次数375,238提交次数1,178,002

题目链接：https://leetcode-cn.com/problems/longest-palindromic-substring

[wengzc]

思路分析：动态规划或中心扩散法

• 只要涉及求最值，没有任何奇技淫巧，一定是穷举所有可能的结果，然后对比得出最值（记住）

• 最值相似题目： 53. 最大子序和、 152. 乘积最大子数组、 300. 最长上升子序列

• 回文串相似题目：647. 回文子串

解法一：动态规划

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
    let len = s.length
    // dp 数组的定义是：子串s[i..j]是否为回文子串
    let dp = new Array(len)
    let begin = 0
    let maxLen = 1
    for (let i = 0; i < len; i++) {
        dp[i] = (new Array(len)).fill(false)
        // base case
        dp[i][i] = true
    }
    // 注意：base case 是斜着的，而且我们推算 dp[i][j] 时需要用到 dp[i+1][j] 和 dp[i][j-1]
    // 总是先得到小子串的回文判定，然后大子串才能参考小子串的判断结果，即填表顺序很重要
    // for (let i = 0; i < len; i++) {
    //     for (let j = i + 1; j < len; j++) {
    //     }
    // } 这样遍历是不对的，存在没有先得到小子串的回文判定，然后求大子串的回文判定的错误情况
    for (let i = len - 1; i >= 0; i--) {
        for (let j = i + 1; j < len; j++) {
            if (s[i] !== s[j]) {
                dp[i][j] = false
            } else {
                if (j - i <= 2) {
                    dp[i][j] = true
                } else {
                    dp[i][j] = dp[i + 1][j - 1]
                }
            }
            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1
                begin = i
            }
        }
    }
    return s.substr(begin, maxLen)
};

解法二：中心扩散法

var longestPalindrome = function (s) {
    let res = ''
    function palindrome(s, l, r) {
        let len = s.length
        while (l >= 0 && r < len && s[l] === s[r]) {
            l--
            r++
        }
        return s.substr(l + 1, r - l - 1)
    }

    let len = s.length
    for (let i = 0; i < len; i++) {
        // 奇数情况
        let s1 = palindrome(s, i, i)
        // 偶数情况
        let s2 = palindrome(s, i, i + 1)
        res = res.length > s1.length ? res : s1
        res = res.length > s2.length ? res : s2
    }
    return res
};