题解 | 最长公共子串

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * longest common substring
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @return string字符串
 */
function LCS( str1 ,  str2 ) {
    // write code here
    let m = str1.length;
    let n = str2.length
    let max = 0
    let position = 0
    let dp = Array.from({length:m+1},()=> new Array(n+1).fill(0))
    for(let i=1;i<=m;i++){
        for(let j=1;j<=n;j++){
            if(str1[i-1] == str2[j-1]){
                dp[i][j] = dp[i-1][j-1] +  1
                if(dp[i][j]>max){
                    max = dp[i][j]
                    position = i
                }
            }
        }
    }
    return str1.substring(position-max,position)
    // console.log(dp)
    
}
module.exports = {
    LCS : LCS
};