编程题:查找两个字符串的最长公共子串的Javascript函数

这是多益网络前端的一道笔试题,这里不得不吐槽一下它的笔试系统是真的垃圾,用习惯牛客网的做题系统,表示这次笔试做的非常难受。

下面分享我的做法

思路:传入两个字符串,先比较谁长谁短,遍历短的字符串,两个for循环,外层循环从最大长度开始遍历,长度逐个递减,内层循环从短字符串的最左边开始截取最大长度的字符串,检查截取的字符串是否在长的字符串里面,  直到找到匹配的字符串

代码:

function findLongestCommonStr(s1, s2) { var commonStr = \'\', L1 = s1.length, L2 = s2.length; // 比较s1,s2的长度,看谁长谁短 var shortStr = L1>L2 ? s2 : s1; var longStr = L1>L2 ? s1 : s2; // 短的字符串的长度 var strLen = shortStr.length; // 遍历短的字符串,从大到小递减 for (let j = strLen; j > 0; j--) { // 不同的长度有总共有i个可能,从做到右遍历 for (let i = 0; i <= strLen - j; i++) { // 截取出短字符串的部分字符串 commonStr = shortStr.substr(i, j); // 为了便于观测运行的过程,打印看一下会直观很多 console.log(\'commonStr:\',commonStr,\'i:\',i,\'j:\',j); // 放在长字符串里看看有没有匹配的,如果有直接返回 if (longStr.indexOf(commonStr) >= 0) return commonStr } } // 没有的话返回空字符串 return \'\' } console.log(findLongestCommonStr("qwer--", "qtrrwqw-")); //qw // 下面的打印的结果,函数执行的过程,i是从哪里开始截取,j是截取的长度 // commonStr: qwer-- i: 0 j: 6 // commonStr: qwer- i: 0 j: 5 // commonStr: wer-- i: 1 j: 5 // commonStr: qwer i: 0 j: 4 // commonStr: wer- i: 1 j: 4 // commonStr: er-- i: 2 j: 4 // commonStr: qwe i: 0 j: 3 // commonStr: wer i: 1 j: 3 // commonStr: er- i: 2 j: 3 // commonStr: r-- i: 3 j: 3 // commonStr: qw i: 0 j: 2

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/zwdpfw.html