JavaScript中的Levenshtein距离
Levenshtein距离
Levenshtein距离是用于测量两个序列之间差异的字符串量度。它是将一个单词转换为另一个单词所需的最少单字符编辑次数。
例如-
考虑，我们有两个字符串-
const str1 = 'hitting'; const str2 = 'kitten';
这两个字符串之间的Levenshtein距离为3，因为我们需要进行这三个编辑-
小猫→被击中（用“h”代替“k”）
hitten→hittin（用“i”代替“e”）
hittin→击中（末尾插入“g”）
我们需要编写一个JavaScript函数，该函数接受两个字符串并计算它们之间的Levenshtein距离。
示例
以下是代码-
const str1 = 'hitting';
const str2 = 'kitten';
const levenshteinDistance = (str1 = '', str2 = '') => {
const track = Array(str2.length + 1).fill(null).map(() =>
Array(str1.length + 1).fill(null));
for (let i = 0; i <= str1.length; i += 1) {
track[0][i] = i;
}
for (let j = 0; j <= str2.length; j += 1) {
track[j][0] = j;
}
for (let j = 1; j <= str2.length; j += 1) {
for (let i = 1; i <= str1.length; i += 1) {
const indicator = str1[i - 1] === str2[j - 1] ? 0 : 1;
track[j][i] = Math.min(
track[j][i - 1] + 1, //删除
track[j - 1][i] + 1, //插入
track[j - 1][i - 1] + indicator, //替代
);
}
}
return track[str2.length][str1.length];
};
console.log(levenshteinDistance(str1, str2));输出结果
以下是控制台上的输出-
3