[JavaScript知识库]最长回文子串

滑动窗口
遍历时截取出所有子字符串，然后判断子字符串是否是回文，然后和最大长度对比输出

// 方案1 滑动窗口法（“时间复杂度高，一般通过不了”）
var longestPalindrome = function(s) {
// 是否为 回文串。（subStr = ‘’ 稍微体现下编程的严谨性）
const isValid = (subStr = ‘’) => {
const l = subStr.length;
let resFlag = true;

    // 边界：i < l/2
    for(let i = 0; i < l/2; i++) {
        // “对称位置”上的字符不相等，那么肯定就不是 回文串 了
        if (subStr[i] !== subStr[(l - 1) - i]) {
            resFlag = false;
            break;
        }
    }

    return resFlag;
}

const l = s.length;
// curMaxLength 当前回文子串的最大长度，范围：[l, 1]
for (let curMaxLength = l; curMaxLength > 0; curMaxLength--) {
    // 在 curMaxLength 下，curStartIndex的有效范围为 [0, ((l + 1) - curMaxLength) )
    for (let curStartIndex = 0; curStartIndex < ((l + 1) - curMaxLength); curStartIndex++) {
        const subStr = s.substr(curStartIndex, curMaxLength);
        // 一旦符合 回文串 ，那么当前子串一定是我们的预期答案（“之一”）
        // 因为我们 curMaxLength 在一次次遍历中在递减
        if (isValid(subStr)) {
            return subStr;
        }
    }
}



// 边界：可能 l为0 、然后直接到这里了，需要返回空字符串（不过题目 1 <= s.length <= 1000 ，故 可省略 ）
return "";

}

动态判划

从最小的子串开始，通过二维数组和首尾索引记录当前子字符串的位置，如果回文置为true,故之后的较长子串只需判断首尾是否相等和首+ 1尾 - 1的子串是否为true即可，最小回文子串a､ aa､ aba构成较长子串，对应的设置逻辑为二维数组相同索引为true、s[i] === s[j] && ((j + 1) - i) < 3时为true

// 方案2 动态规划，(s[i] === s[j] && dp[i + 1][j - 1]) || (s[i] === s[j] && ((j + 1) - i) < 3[i] )
var longestPalindrome = function(s) {
const l = s.length,
// 1）含义：s[i][j] 表示s[i, j]是否为回文串（双闭区间）
// 初始化1：dp， n*n 个值都初始化为 false
dp = new Array(l).fill(false).map(item => new Array(l).fill(false));
// 当前 最长回文子串 的开始下标、最大长度
let maxStartIndex = 0,
// 边界：maxLength 初始化为1。不然会有问题、可自行思考~
maxLength = 1;

// 初始化2：dp对角线上值 均为 true 
for (let i = 0; i < l; i++) {
    for(let j = 0; j < l; j++) {
        if (i === j) {
            dp[i][j] = true;
        }
    }
}

// 2）状态转移方程：
// s[i][j] = (s[i] === s[j] && dp[i + 1][j - 1]) || (s[i] === s[j] && ((j + 1) - i) < 3)
// s[i][j] = (当前首、尾字符相同 && 首、尾各往中间缩1位依旧是回文串) 
// 或 (当前首、尾字符相同 && 当前首、尾位置间隔 < 3) 如 "bb" 这种长度小于3时，只要保证 首、尾字符相同即可
for (let j = 1; j < l; j++) {
    for(let i = 0; i < j; i++) {
        if ((s[i] === s[j] && dp[i + 1][j - 1]) || (s[i] === s[j] && ((j + 1) - i) < 3)) {
            dp[i][j] = true;
            // 当前s[i, j]为回文串了，才看是否需要更新 maxStartIndex、maxLength 值
            // 3）当 s[i, j]为回文串 && (j + 1) - i) > maxLength 时，更新 maxStartIndex、maxLength 值
            if (((j + 1) - i) > maxLength) {
                maxStartIndex = i;
                maxLength = ((j + 1) - i);
            }
        } else {
            dp[i][j] = false;
        }
    }
}

// 最后根据 “我们所维护的” maxStartIndex, maxLength 得出相应的子串
return s.substr(maxStartIndex, maxLength);

}