最近在看《数据结构与算法JavaScript描述》这本书时,遇到了这个问题。结果我把代码复制到本地后,发现得不到正确的结果,于是对代码进行了改进。
function lcs(word1, word2) {
word1 = '-' + word1;
word2 = '+' + word2;
var max = 0;
var index = 0;
var lcsarr = new Array(word1.length);
for (var i = 0; i < lcsarr.length; i++) {
lcsarr[i] = new Array(word2.length);
for (var j = 0; j < lcsarr[0].length; j++) {
lcsarr[i][j] = 0;
}
}
for (var i = 1; i < lcsarr.length; i++) {
for (var j = 1; j < lcsarr[0].length; j++) {
if (word1[i] == word2[j]) {
lcsarr[i][j] = lcsarr[i-1][j-1] + 1;
}
if (max < lcsarr[i][j]) {
max = lcsarr[i][j];
index = i;
}
}
}
return word1.slice(index+1-max,index+1);
}
不过此代码有缺陷,在最长公共字符串有多个的情况下,只能找到第一个。
网友评论