forked from TheAlgorithms/JavaScript
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLevenshteinDistance.js
More file actions
42 lines (36 loc) · 947 Bytes
/
Copy pathLevenshteinDistance.js
File metadata and controls
42 lines (36 loc) · 947 Bytes
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
31
32
33
34
35
36
37
38
39
40
41
42
/**
* 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
} else if (b < a && b < c) {
return b
} else {
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]
}
export { calculate }