JavaScript 中的编辑距离

javascriptweb developmentfront end technologyobject oriented programming更新于 2024/2/21 13:32:17

编辑距离

编辑距离是用于测量两个序列之间差异的字符串度量。它是将一个单词更改为另一个单词所需的最小单字符编辑次数。

例如 −

考虑一下，我们有这两个字符串 −

const str1 = 'hitting';
const str2 = 'kitten';

这两个字符串之间的编辑距离为 3，因为我们需要进行这三次编辑 −

kitten → hitten (用"h"替换"k")
hitten → hittin (用"i"替换"e")
hittin → hitting (在末尾插入"g")

我们需要编写一个 JavaScript 函数，该函数接受两个字符串并计算它们之间的编辑距离。

示例

以下是代码 −

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));