最长回文子串

题目描述

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

示例 1： 输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。

示例 2： 输入：s = “cbbd”
输出：“bb”

思路&js代码

1、动态规划

我们使用一个二维数组 dp[i][j] 来表示：字符串 s 中下标从 i 到 j 的子串 s[i..j] 是否为回文子串。 状态转移规则：

• 当 s[i] !== s[j]，显然 s[i..j] 不是回文串；
• 当 s[i] === s[j] 时： - 若 j - i < 3（子串长度为2或3），只要两端字符相等就是回文串； - 否则要看内部子串 dp[i + 1][j - 1] 是否为回文。

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    const len = s.length;
    if (len < 2) return s; // 长度小于2，直接返回原串
 
    let maxLen = 1; // 初始化最大长度
    let begin = 0;  // 初始化起始位置
    const dp = Array.from({ length: len }, () => Array(len).fill(false));
 
    // 所有长度为1的子串都是回文串
    for (let i = 0; i < len; i++) {
        dp[i][i] = true;
    }
 
    const charArray = s.split('');
 
    // 枚举子串结束位置 j
    for (let j = 1; j < len; j++) {
        // 枚举子串起始位置 i（必须 i < j）
        for (let i = 0; i < j; i++) {
            if (charArray[i] !== charArray[j]) {
                dp[i][j] = false;
            } else {
                if (j - i < 3) {
                    dp[i][j] = true; // 长度为2或3，只要两端相等就是回文
                } 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.substring(begin, begin + maxLen);
};