Skip to content

在JavaScript中计算两个字符串的Levenshtein距离

定义

Levenshtein距离是衡量两个字符串之间差异的度量标准。它被定义为将一个字符串转变为另一个字符串所需的最小单字符编辑次数（插入、删除或替换）。它有时也被称为_编辑距离_，尽管这也可能指不同的距离度量标准。

实现

以下实现基于Wagner-Fischer算法。它使用一个二维数组来存储两个字符串所有前缀之间的距离。数组的最后一行的最后一个元素包含了两个字符串之间的Levenshtein距离。

  1. 首先检查每个字符串的length。如果其中一个字符串的长度为零，则返回另一个字符串的length。
  2. 创建一个空的二维数组。使用一个for循环遍历目标字符串的字母，并使用嵌套的for循环遍历源字符串的字母。
  3. 计算目标字符串中对应于目标和源的i - 1和j - 1的字母的替换成本（如果它们相同则为0，否则为1）。
  4. 使用Math.min()将二维数组中的每个元素填充为上方单元格加一、左侧单元格加一或左上方单元格加上先前计算的成本的最小值。
  5. 返回生成的数组的最后一行的最后一个元素。这就是两个字符串之间的Levenshtein距离。
const levenshteinDistance = (s, t) => {
  if (!s.length) return t.length;
  if (!t.length) return s.length;
  const arr = [];
  for (let i = 0; i <= t.length; i++) {
    arr[i] = [i];
    for (let j = 1; j <= s.length; j++) {
      arr[i][j] =
        i === 0
          ? j
          : Math.min(
              arr[i - 1][j] + 1,
              arr[i][j - 1] + 1,
              arr[i - 1][j - 1] + (s[j - 1] === t[i - 1] ? 0 : 1)
            );
    }
  }
  return arr[t.length][s.length];
};

levenshteinDistance('duck', 'dark'); // 2
levenshteinDistance('foo', 'foobar'); // 3

复杂度

该算法的时间复杂度为O(mn)，其中m和n分别是两个字符串的长度。空间复杂度也是O(mn)，因为我们创建了一个相同大小的二维数组。

一种可能的修改是将空间复杂度降低到O(min(m, n))，使用两个长度为min(m, n) + 1的数组代替2D数组。这是基于算法只需要在任何给定时间跟踪2D数组的前一行的事实。