题解 | 最长公共子串

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