题解 | 最长公共子串

最长公共子串

https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 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
};

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-09 16:15
我应届生,去年10月份开始在这家公司实习,到今年10月份正好一年想(实习+试用期),在想要不要提前9月份就离职,这样好找工作些,但又差一个月满一年,又怕10月份国庆回来离职,容易错过了下半年的金九银十,到年底容易gap到年后
小破站_程序员YT:说这家公司不好吧,你干了快一年 说这家公司好吧,你刚毕业就想跑路说你不懂行情吧,你怕错过金九银十说 你懂行情吧,校招阶段在实习,毕业社招想换工作 哥们,我该怎么劝你留下来呢
应届生,你找到工作了吗
点赞 评论 收藏
分享
头顶尖尖的程序员:我是26届的不太懂,25届不应该是找的正式工作吗?为什么还在找实习?大四还实习的话是为了能转正的的岗位吗
点赞 评论 收藏
分享
头顶尖尖的程序员:我也是面了三四次才放平心态的。准备好自我介绍,不一定要背熟,可以记事本写下来读。全程控制语速,所有问题都先思考几秒,不要急着答,不要打断面试官说话。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务