LevenshteinDistance [莱文斯坦距离]
# 介绍
莱文斯坦距离，又称 Levenshtein 距离，是编辑距离的一种。指两个字串之间，由一个转成另一个所需的最少编辑操作次数。
允许的编辑操作包括：
- 将一个字符替换成另一个字符
- 插入一个字符
- 删除一个字符
# 实现
# JavaScript
/**
* A Dynamic Programming based solution for calculation of the Levenshtein Distance
* https://en.wikipedia.org/wiki/Levenshtein_distance
*/
function minimum (a, b, c) {
if (a < b && a < c) return a;
if (b < a && b < c) return b;
return c
}
function costOfSubstitution (x, y) {
return x === y ? 0 : 1
}
// Levenshtein distance between x and y
function calculate (x, y) {
const dp = new Array(x.length + 1)
for (let i = 0; i < x.length + 1; i++) dp[i] = new Array(y.length + 1);
for (let i = 0; i < x.length + 1; i++) {
for (let j = 0; j < y.length + 1; j++) {
if (i === 0) dp[i][j] = j;
else if (j === 0) dp[i][j] = i;
else dp[i][j] = minimum(dp[i - 1][j - 1] + costOfSubstitution(x.charAt(i - 1), y.charAt(j - 1)), dp[i - 1][j] + 1, dp[i][j - 1] + 1);
}
}
return dp[x.length][y.length]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# 参考
编辑 (opens new window)
上次更新: 2022/10/25, 20:46:09