forked from thuva4/Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathedit_distance.py
More file actions
31 lines (24 loc) · 932 Bytes
/
edit_distance.py
File metadata and controls
31 lines (24 loc) · 932 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
# Helpful tutorial: https://www.youtube.com/watch?v=We3YDTzNXEk
# Useful link: https://en.wikipedia.org/wiki/Edit_distance
def get_edit_distance(s1, s2):
l1 = len(s1) + 1
l2 = len(s2) + 1
edit_table = {}
for i in range(l1):
edit_table[i, 0] = i
for j in range(l2):
edit_table[0, j] = j
for i in range(1, l1):
for j in range(1, l2):
edit_table[i, j] = min(edit_table[i - 1, j], edit_table[i, j - 1],
edit_table[i - 1, j - 1])
if s1[i - 1] != s2[j - 1]:
edit_table[i, j] += 1
return edit_table[i, j]
if __name__ == '__main__':
# returns 1 as adding 'a' in 2nd postion to
# 'hello' will make it 'haello'
print get_edit_distance('hello', 'haello')
# returns 2 as replacing 'o' in 'redor' and adding 'e' at the end will make
# 'redare'
print get_edit_distance('redor', 'redare')