forked from mission-peace/interview
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy patheditdistance.py
More file actions
82 lines (66 loc) · 2.19 KB
/
Copy patheditdistance.py
File metadata and controls
82 lines (66 loc) · 2.19 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
"""
Problem Statement
=================
Given two strings str1 and str2, find the minimum number of edits (edit one character to another, delete char from str1
or delete char from str2) to change str1 to str2.
Video
-----
* https://youtu.be/We3YDTzNXEk
Analysis
--------
* DP Runtime : O(len(str1) * len(str2))
* Recursive Solution: Exponential (O(3^(m+n-1)))
Reference
---------
* https://www.clear.rice.edu/comp130/12spring/editdist/
"""
def print_edits(T, str1, str2):
i = len(T) - 1
j = len(T[0]) - 1
while True:
if i == 0 or j == 0:
break
if str2[i - 1] == str1[j - 1]:
i -= 1
j -= 1
elif T[i][j] == T[i - 1][j - 1] + 1:
print "Edit %s in string1 to %s in string2." % (str1[j - 1], str2[i - 1])
i -= 1
j -= 1
elif T[i][j] == T[i - 1][j] + 1:
print "Delete %s in string2." % str2[i - 1]
i -= 1
elif T[i][j] == T[i][j - 1] + 1:
print "Delete %s in string1." % str1[j - 1]
j -= 1
def min_edit_distance(str1, str2):
rows = len(str2) + 1
cols = len(str1) + 1
T = [[0 for _ in range(cols)] for _ in range(rows)]
for j in range(cols):
T[0][j] = j
for i in range(rows):
T[i][0] = i
for i in range(1, rows):
for j in range(1, cols):
if str2[i - 1] == str1[j - 1]:
T[i][j] = T[i - 1][j - 1]
else:
T[i][j] = 1 + min(T[i - 1][j - 1], T[i - 1][j], T[i][j - 1])
print_edits(T, str1, str2)
return T[rows - 1][cols - 1]
def min_edit_distance_recursive(str1, str2):
i = len(str1)
j = len(str2)
if i == 0: return j
if j == 0: return i
return min(min_edit_distance_recursive(str1[:i - 1], str2) + 1,
min_edit_distance_recursive(str1, str2[:j - 1]) + 1,
min_edit_distance_recursive(str1[:i - 1], str2[:j - 1]) + (1 if str1[i - 1] != str2[j - 1] else 0))
if __name__ == '__main__':
str1 = "azced"
str2 = "abcdef"
expected = 3
assert expected == min_edit_distance(str1, str2)
assert expected == min_edit_distance(str2, str1)
assert expected == min_edit_distance_recursive(str1, str2)