解题灵感来自最长公共子序列,时间复复杂度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 '';
};
