forked from vokoshyv/codewarsstuff
-
Notifications
You must be signed in to change notification settings - Fork 0
/
levenshteinDistance
39 lines (32 loc) · 1.2 KB
/
levenshteinDistance
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
var LevenshteinDistance(string s, string t)
{
// degenerate cases
if (s == t) return 0;
if (s.Length == 0) return t.Length;
if (t.Length == 0) return s.Length;
// create two work vectors of integer distances
var[] v0 = new var[t.Length + 1];
var[] v1 = new var[t.Length + 1];
// initialize v0 (the previous row of distances)
// this row is A[0][i]: edit distance for an empty s
// the distance is just the number of characters to delete from t
for (var i = 0; i < v0.Length; i++)
v0[i] = i;
for (var i = 0; i < s.Length; i++)
{
// calculate v1 (current row distances) from the previous row v0
// first element of v1 is A[i+1][0]
// edit distance is delete (i+1) chars from s to match empty t
v1[0] = i + 1;
// use formula to fill in the rest of the row
for (var j = 0; j < t.Length; j++)
{
var cost = (s[i] == t[j]) ? 0 : 1;
v1[j + 1] = Minimum(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost);
}
// copy v1 (current row) to v0 (previous row) for next iteration
for (var j = 0; j < v0.Length; j++)
v0[j] = v1[j];
}
return v1[t.Length];
}