最长回文子串

[xszi]

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

示例 1：

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

示例 2：

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

leetcode

[xszi]

动态规划关键是找到初始状态和状态转移方程。

初始状态

left = right: dp[left][right] = true。

状态转移方程

dp[left][right] = true
且s(left-1) === s(right+1)
此时 dp[left-1][right+1] = true。

代码求解

const longestPalindrome = (s) => {
    if (s == null || s.length < 2) {
        return s;
    }
    let strLen = s.length;
    let maxStart = 0; //最长回文串的起点
    let maxEnd = 0; //最长回文串的终点
    let maxLen = 1; //最长回文串的长度

    let dp = new Array(s.length); //表格有10行
    for (let i = 0; i < s.length; i++) {
        dp[i] = new Array(s.length); //每行有10列
    }

    for (let r = 1; r < strLen; r++) {
        for (let l = 0; l < r; l++) {
            if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
                dp[l][r] = true;
                if (r - l + 1 > maxLen) {
                    maxLen = r - l + 1;
                    maxStart = l;
                    maxEnd = r;
                }
            }

        }

    }
    return s.substring(maxStart, maxEnd + 1);
}

const s = 'babad'
console.log(longestPalindrome(s));