levenshtein

计算两个字符串之间的 Levenshtein 距离（编辑距离）。

函数签名

function levenshtein(str1: string, str2: string): number

参数

参数名	类型	必填	说明
str1	string	是	第一个字符串
str2	string	是	第二个字符串

返回值

类型	说明
number	两个字符串之间的 Levenshtein 距离（最少编辑操作次数）

工作原理

使用动态规划算法计算编辑距离：

1. 特殊情况处理：

   • 如果两个字符串相同，返回 0
   • 如果其中一个为空，返回另一个的长度

2. 初始化矩阵：

   • 创建二维矩阵 matrix[i][j]，大小为 (str2.length + 1) × (str1.length + 1)
   • 第一列初始化为 [0, 1, 2, ..., str2.length]
   • 第一行初始化为 [0, 1, 2, ..., str1.length]

3. 填充矩阵：

   • 遍历矩阵的每个单元格
   • 如果当前字符相同：matrix[i][j] = matrix[i-1][j-1]
   • 如果当前字符不同：取三种操作的最小值 + 1
     • 替换：matrix[i-1][j-1] + 1
     • 插入：matrix[i][j-1] + 1
     • 删除：matrix[i-1][j] + 1

4. 返回结果：矩阵右下角的值 matrix[str2.length][str1.length]

算法的时间复杂度为 O(m×n)，空间复杂度为 O(m×n)，其中 m 和 n 是两个字符串的长度。