第五题 - 最长回文子串

[laizimo]

题目描述

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

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

示例 2：
输入: "cbbd"
输出: "bb"

算法

动态规划

答案

/**
 * 动态规划
 */
var longestPalindrome = function(s) {
    //#1 取字符串长度
    const len = s.length;
    let res = ''

    //#2 建立二维矩阵
    const dp = Array.from(new Array(len), () => new Array(len).fill(0));
    
    //#3 从尾部开始遍历字符串，方便存储之前的状态
    for (let i = len - 1; i >= 0; i--) {
        for (let j = i; j < len; j++) {
            //#4 判断dp[i][j]的情况，需要先判断字符串s[i]和s[j]，在判断子字符串是否是回文
            dp[i][j] = s[i] === s[j] && (j - i < 2 || dp[i + 1][j - 1]);
            //#5 如果是回文，则去判断长度，赋值
            if (dp[i][j] && j - i + 1 >= res.length) {
                res = s.substr(i, j - i + 1);
            }
        }
    }
    return res;
};