LC 5.最长回文子串

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

暴力解法

1

动态规划

function longestPalindrome(str) {
    const { length } = str;

    const dp = new Array(length)
        .fill([])
        .map(() => new Array(length).fill(false));

    let res = str[0];
    for (let i = 0; i < length; i++) {
        dp[i][i] = true; // 自己本身一定是回文的
    }

    if (length === 1) {
        return str;
    }

    for (let i = 1; i < length; i++) {
        for (let j = 0; j < i; j++) {
            // 边界不等，证明这一段不是回文
            if (str[i] !== str[j]) {
                dp[j][i] = false;
            } else {
                if (i - j < 3) {
                    // 边界间隔小于3时，则一定为回文
                    dp[j][i] = true;
                } else {
                    // 边界间隔大于3时，则要判断内部是否是回文
                    dp[j][i] = dp[j + 1][i - 1];
                }
            }

            if (dp[j][i] && i - j + 1 > res.length) {
                res = str.substring(j, i + 1);
                console.log('res:', res);
            }
        }
    }
    return res;
}