一个一百行代码不到的基于动态规划lcs算法的迷你文本比较器
github地址：https://github.com/kimlongli/min-diff
function lcs(arr1, arr2) {
matrix = [];
for(i = 0; i < arr1.length + 1; i++) {
matrix.push([]);
for(j = 0; j < arr2.length + 1; j++) {
matrix[i].push(0);
}
}
for(i = 1; i < arr1.length + 1; i++) {
for(j = 1; j < arr2.length + 1; j++) {
if(arr1[i - 1] == arr2[j - 1]) {
matrix[i][j] = matrix[i - 1][j - 1] + 1;
}
else if(matrix[i - 1][j] >= matrix[i][j - 1]) {
matrix[i][j] = matrix[i - 1][j];
}
else if(matrix[i - 1][j] < matrix[i][j - 1]) {
matrix[i][j] = matrix[i][j - 1];
}
else {
console.log("unexpected error");
}
}
}
return matrix[i - 1][j - 1];
}
function lcs(arr1, arr2) {
matrix = [];
route = [];
for(i = 0; i < arr1.length + 1; i++) {
matrix.push([]);
route.push([]);
for(j = 0; j < arr2.length + 1; j++) {
matrix[i].push(0);
route[i].push([]);
}
}
for(i = 1; i < arr1.length + 1; i++) {
for(j = 1; j < arr2.length + 1; j++) {
if(arr1[i - 1] == arr2[j - 1]) {
matrix[i][j] = matrix[i - 1][j - 1] + 1;
route[i][j] = [[i - 1, j - 1]].concat(route[i - 1][j - 1]);
}
else if(matrix[i - 1][j] >= matrix[i][j - 1]) {
matrix[i][j] = matrix[i - 1][j];
route[i][j] = route[i - 1][j];
}
else if(matrix[i - 1][j] < matrix[i][j - 1]) {
matrix[i][j] = matrix[i][j - 1];
route[i][j] = route[i][j - 1];
}
}
}
return route[i - 1][j - 1];
}