-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathstring.edit.distance.js
More file actions
85 lines (71 loc) · 2 KB
/
string.edit.distance.js
File metadata and controls
85 lines (71 loc) · 2 KB
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/*
* @title: String Edits
* @description: find number of edits needed for str1 to str2
* @author: Thorsten Kober
* @email: [email protected]
*/
/*
Given two strings str1 and str2 and below operations that can performed
on str1. Find minimum number of edits (operations) required to convert
‘str1’ into ‘str2’.
Insert
Remove
Replace
All of the above operations are of equal cost.
*/
// recursive
function numEditsAway(str1, str2, index1, index2) {
if (index1 === 0) return index2;
if (index2 === 0) return index1;
if (str1[index1 - 1] === str2[index2 - 1]) {
return numEditsAway(str1, str2, index1 - 1, index2 - 1);
}
return 1 + Math.min(
numEditsAway(str1, str2, index1 - 1, index2), // remove
numEditsAway(str1, str2, index1, index2 - 1), // insert
numEditsAway(str1, str2, index1 - 1, index2 - 1), // replace
);
}
// tabulation
function numEditsAway2(str1, str2) {
const length1 = str1.length;
const length2 = str2.length;
const result = [];
for (let i = 0; i <= length1; i++) {
result[i] = [];
for (let j = 0; j <= length2; j++) {
result[i][j] = 0;
}
}
for (let i = 0; i <= length1; i++) {
result[i][0] = i;
}
for (let i = 0; i <= length2; i++) {
result[0][i] = i;
}
for (let i = 1; i <= length1; i++) {
for (let j = 1; j <= length2; j++) {
if (str1[i - 1] === str2[j - 1]) {
result[i][j] = result[i - 1][j - 1];
} else {
result[i][j] = 1 + Math.min(
result[i - 1][j], // remove
result[i][j - 1], // insert
result[i - 1][j - 1], // replace
);
}
}
}
return result[length1][length2];
}
// npx jest algorithms/string/string.edit.distance.js
test('numEditsAway()', () => {
const str1 = 'saturday';
const str2 = 'sunday';
expect(numEditsAway(str1, str2, str1.length, str2.length)).toEqual(3);
});
test('numEditsAway2()', () => {
const str1 = 'saturday';
const str2 = 'sunday';
expect(numEditsAway2(str1, str2)).toEqual(3);
});