题解 | #最长公共子串#

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * longest common substring
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @return string字符串
 */
function LCS(str1, str2) {
    // write code here
    if (str1.length == 0 || str2.length == 0) return -1;
    // 动态规划的状态转移方程：
    // if(str1[i]==str2[j]){dp[i-1][j-1]+str1[i]}

    // 吸取前面的经验，给把i=0和j=0的地方全部置为空字符串
    str1 = "_" + str1;
    str2 = "_" + str2;
    let maxL = 0;
    let maxP = [0, 0];
    let dp = [];
    for (let i = 0; i < str1.length + 1; i++) {
        if (i == 0) {
            dp.push(new Array(str2.length).fill(""));
            continue;
        }
        dp.push([]);
        for (let j = 0; j < str2.length; j++) {
            if (j == 0) {
                dp[i].push("");
                continue;
            }
            if (i == 10 && j == 8) {
                console.log(dp[i][j]);
                console.log(dp[i][j]);
            }
            if (str1[i] == str2[j]) {
                dp[i].push(dp[i - 1][j - 1] + str1[i]);
                // console.log(dp)
                if (!(maxL > dp[i][j].length)) {
                    maxL = dp[i][j].length;
                    maxP = [i, j];
                }
            } else {
                dp[i].push("");
            }
        }
    }

    return dp[maxP[0]][maxP[1]];
}
module.exports = {
    LCS: LCS,
};