5.最长回文子串

[Geekhyt]

原题连接

如果一个字符串 aba 是一个回文串，那么在它的左右分别添加一个相同的字符 a，那么它一定还是一个回文串 aabaa。

我们可以用 dp[i][j] 表示 s 中从 i 到 j (包括 i 和 j) 是否可以形成回文串，将上面这段话翻译成代码，列出状态转移方程。

• dp[i][j] === true 是回文串
• dp[i][j] === false 不是回文串

状态转移方程

s[i] === s[j] && dp[i][j] = dp[i + 1][j - 1]

边界处理

需要考虑 j - i < 2 的情况，此时子串长度为 0 或 1。

例如：a，aa，对称点分别是字符本身和两个字符中间的虚拟点。

双重循环，不断向外延伸尝试得到可能的最大回文串长度。第一层倒着循环，是因为 dp[i] 依赖于 dp[i + 1]。

const longestPalindrome = function (s) {
    const len = s.length
    const dp = Array.from(new Array(len), () => new Array(len).fill(0))
    let res = ''
    for (let i = len - 1; i >= 0; i--) {
        for (let j = i; j < len; 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.slice(i, j + 1)
            }
        }
    }
    return res
}

• 时间复杂度：O(n^2)
• 空间复杂度：O(n^2)