博客

BM66 最长公共子串


描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串。题目保证str1和str2的最长公共子串存在且唯一。

示例1

输入：

“1AB2345CD”,“12345EF”

返回值：

“2345”

解题：


这是一套典型的动态规划的题目，算是中等题

/**
 * longest common substring
 * @param str1 string字符串 the string
 * @param str2 string字符串 the string
 * @return string字符串
 */
function LCS( str1 ,  str2 ) {
    // write code here
    if(str1.length === 0 || str2.length === 0) {
        return ''
    }
    if(str1.length > str2.length) { // 保证str1是最短的
        [str1, str2] = [str2, str1]
    }
    // max用来记录字串的长度
    let max = 0, res = ''
    for(let i = 0; i < str1.length; i++) {
        // 通过slice来截取字串
        const tmp = str1.slice(i - max, i + 1)
        console.log(tmp)
        if(str2.indexOf(tmp) >= 0) {
            res = tmp
            // 如果相等则长度+1
            max++
        }
    }
    return res
}
module.exports = {
    LCS : LCS
};