题解 | #最长公共子串#

参考这篇文章写js版本https://www.cnblogs.com/fanguangdexiaoyuer/p/11281179.html，动态规划算法

function LCS( str1 ,  str2 ) {
    // write code here
    // write code here
    var s1 = str1.split('');
    var s2 = str2.split('');
    var dp = new Array(s1.length);
    for (let i = 0; i < s1.length; i++) {
        dp[i] = new Array(s2.length);
    }
    console.log(dp);
    var strLength = 0;
    var res = '';
    for (let i = 0; i < s1.length; i++) {
        for (let j = 0; j < s2.length; j++) {
            if (s1[i] === s2[j]) {
                if (i === 0 || j === 0) {
                    dp[i][j] = s1[i];
                } else {
                    dp[i][j] = dp[i - 1][j - 1] + s1[i];
                    if (strLength < dp[i][j].length) {
                        strLength = dp[i][j].length;
                        res = dp[i][j];
                        // console.log(res);
                    }
                }
            } else {
                dp[i][j] = '&';
            }
        }
    }
    res = res.split('');
    for (let i = 0; i < res.length; i++) {
        if (res[i] === '&') {
            res.splice(i, 1);
        }
    }
    res = res.join('');
    // console.log(dp);
    return res;
}