动态规划-最长公共子串

解题灵感来自最长公共子序列,时间复复杂度O(n x m)，空间复杂度0(m x n)
测试用例地址

let longestCommonSubStr = (str1,str2)=>{
    let n = str1.length;
    let m = str2.length;
    if(n === 0 || m === 0){
        return ''
    }
    n += 1;
    m += 1;
    let dp = new Array(n);
    for(let i = 0; i < n; i ++){
        dp[i] = new Array(m).fill(0);

    }

    let maxLength = 0;
    //相对于str1的坐标
    let endIndex = 0;
    for(let i = 1; i < n;i ++){
        for(j = 1; j < m;j ++){
            if(str1[i - 1] === str2[j - 1]){
                dp[i][j] = dp[i - 1][j - 1] + 1
            }
            if(dp[i][j] > maxLength){
                maxLength = dp[i][j];
                endIndex = i
            }
        }
    }
    if(maxLength > 0){
        return str1.substr( endIndex - maxLength,maxLength)
    }
    return '';
};