Levenshtein Distance，也称为 Edit Distance，用于计算将一个字符串转换为另一个字符串所需的最少编辑操作数量。
标准操作包括：
- Insert
- Delete
- Replace
每次操作通常成本为 1。
例如：
cat → cut
只需要把 a 替换成 u：
Distance = 1
经典例子
kitten → sitting
一种最优转换过程是：
kitten → sitten
sitten → sittin
sittin → sitting
因此：
Distance = 3
动态规划定义
定义：
dp[i][j]
表示将第一个字符串前 i 个字符转换为第二个字符串前 j 个字符所需的最少操作数。
基础状态：
dp[0][j] = j
dp[i][0] = i
如果当前字符相同：
dp[i][j] = dp[i - 1][j - 1]
如果不同：
dp[i][j] = 1 + min(
dp[i - 1][j],
dp[i][j - 1],
dp[i - 1][j - 1]
)
分别对应 Delete、Insert 和 Replace。
TypeScript 实现
function levenshteinDistance(a: string, b: string): number {
const dp = Array.from(
{ length: a.length + 1 },
() => new Array(b.length + 1).fill(0)
);
for (let i = 0; i <= a.length; i++) {
dp[i][0] = i;
}
for (let j = 0; j <= b.length; j++) {
dp[0][j] = j;
}
for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
if (a[i - 1] === b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(
dp[i - 1][j],
dp[i][j - 1],
dp[i - 1][j - 1]
);
}
}
}
return dp[a.length][b.length];
}
复杂度
若两个字符串长度为 n 和 m：
Time Complexity: O(n × m)
Space Complexity: O(n × m)
如果只保存当前行和上一行，空间可以优化为：
O(min(n, m))
拼写检查
用户可能输入：
programing
而正确单词是：
programming
两者距离只有 1，因此可以作为高质量的拼写建议。
Fuzzy Search
例如数据库中是：
Alexander
用户搜索：
Alexnder
虽然 Exact Match 失败，但 Levenshtein Distance 可以发现二者非常接近。
CRM 与重复数据检测
CRM 中可能存在：
Arian Soleimanzadeh
Arian Soleimanzade
较小的 Edit Distance 可以作为 Duplicate Detection 的一个信号。
实际系统仍然应该结合 Email、Phone 等其他字段判断。
其他应用
- Spell Checking
- Fuzzy Search
- OCR Correction
- NLP
- Data Cleaning
- Record Matching
- Bioinformatics
与 Hamming Distance 的区别
Hamming Distance 只比较对应位置，并通常要求两个字符串长度相同。
Levenshtein 支持 Insert 和 Delete。
例如：
cat → cats
Levenshtein Distance 为 1。
Weighted Edit Distance
操作成本也可以不同：
Insert = 1
Delete = 1
Replace = 2
这样可以根据实际业务需求调整字符串相似度模型。
技术面试中的经典问题
一个常见题目是：
给定
word1和word2，求使用 Insert、Delete 和 Replace 将前者转换为后者的最少操作次数。
例如：
horse → ros
答案是：
3
常见错误
由于第 0 行和第 0 列表示空字符串，因此访问字符时通常使用：
a[i - 1]
b[j - 1]
如果字符相同，也不应该额外增加操作成本。
总结
Levenshtein Distance 计算两个字符串之间最少的 Insert、Delete 和 Replace 操作数量。
标准动态规划方案复杂度为：
Time: O(n × m)
Space: O(n × m)
除了算法题之外，它还广泛应用于 Fuzzy Search、拼写检查、CRM 去重、数据清洗、OCR 和 NLP。