动态规划10：最长回文子串

题目

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

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

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

分析

求解最长回文子串，显然需要知道起始字符串的位置。
令DP[i][j]表示起始位置是i,j的子串的回文长度
则DP[i][j] = str[i] === str[j] ? DP[i+1][j-1] + 2 : 0;

再考虑子串为aca或者bb,时，DP[i][j] = j+1-i;

可以看到DP[i][j]与DP[i+1][j-1]有关，所以遍历时i从大到小，j从小到大。

function solution(str) {
    const len = str.length;
    let maxStr = str.slice(0,1);

    let DP = [];
    for(let i=0;i<len;i++) {
        DP[i] = [];
        DP[i][i] = 1;
    }

    for(let i=len-2; i>=0; i--) {
        for(let j=i+1; j<len; j++) {
            if(str[i] === str[j]) {
                if(j-i<3) {
                    DP[i][j] = j+1-i;
                } else if(DP[i+1][j-1]) {
                    DP[i][j] = DP[i+1][j-1] + 2;
                }
                if(DP[i][j] > maxStr.length ){
                    maxStr = str.slice(i, j+1);
                }
            } else {
                DP[i][j] = 0;
            }
        }
    }
    return maxStr;
}

下面的解法，DP[i][j]中存储当前字符串是否为回文，再使用left, right变量来记录当前最大回文子串的位置。

function solution(str) {
    const len = str.length;
    let maxLen = 1;
    let left = 0;
    let right = 1;

    let DP = [];
    for(let i=0;i<len;i++) {
        DP[i] = [];
        DP[i][i] = 1;
    }

    for(let i=len-2; i>=0; i--) {
        for(let j=i+1; j<len; j++) {
            if(str[i] === str[j] && (j-i<3 || DP[i+1][j-1])) {
                DP[i][j] = 1;
                if(j-i+1 > maxLen) {
                    maxLen = j-i+1;
                    left = i;
                    right = j;
                }
            } else {
                DP[i][j] = 0;
            }
        }
    }
    return str.slice(left, right+1);
}