Repository navigation
Expand file tree
/
Copy pathedit_distance.py
More file actions
103 lines (87 loc) · 3.35 KB
/
Copy pathedit_distance.py
File metadata and controls
103 lines (87 loc) · 3.35 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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
"""
Author : Turfa Auliarachman
Date : October 12, 2016
This is a pure Python implementation of Dynamic Programming solution to the edit
distance problem.
The problem is :
Given two strings A and B. Find the minimum number of operations to string B such that
A = B. The permitted operations are removal, insertion, and substitution.
"""
class EditDistance:
"""
Use :
solver = EditDistance()
editDistanceResult = solver.solve(firstString, secondString)
"""
def __init__(self):
self.word1 = ""
self.word2 = ""
self.dp = []
def __min_dist_top_down_dp(self, m: int, n: int) -> int:
if m == -1:
return n + 1
elif n == -1:
return m + 1
elif self.dp[m][n] > -1:
return self.dp[m][n]
else:
if self.word1[m] == self.word2[n]:
self.dp[m][n] = self.__min_dist_top_down_dp(m - 1, n - 1)
else:
insert = self.__min_dist_top_down_dp(m, n - 1)
delete = self.__min_dist_top_down_dp(m - 1, n)
replace = self.__min_dist_top_down_dp(m - 1, n - 1)
self.dp[m][n] = 1 + min(insert, delete, replace)
return self.dp[m][n]
def min_dist_top_down(self, word1: str, word2: str) -> int:
"""
>>> EditDistance().min_dist_top_down("intention", "execution")
5
>>> EditDistance().min_dist_top_down("intention", "")
9
>>> EditDistance().min_dist_top_down("", "")
0
"""
self.word1 = word1
self.word2 = word2
self.dp = [[-1 for _ in range(len(word2))] for _ in range(len(word1))]
return self.__min_dist_top_down_dp(len(word1) - 1, len(word2) - 1)
def min_dist_bottom_up(self, word1: str, word2: str) -> int:
"""
>>> EditDistance().min_dist_bottom_up("intention", "execution")
5
>>> EditDistance().min_dist_bottom_up("intention", "")
9
>>> EditDistance().min_dist_bottom_up("", "")
0
"""
self.word1 = word1
self.word2 = word2
m = len(word1)
n = len(word2)
self.dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
for i in range(m + 1):
for j in range(n + 1):
if i == 0: # first string is empty
self.dp[i][j] = j
elif j == 0: # second string is empty
self.dp[i][j] = i
elif word1[i - 1] == word2[j - 1]: # last characters are equal
self.dp[i][j] = self.dp[i - 1][j - 1]
else:
insert = self.dp[i][j - 1]
delete = self.dp[i - 1][j]
replace = self.dp[i - 1][j - 1]
self.dp[i][j] = 1 + min(insert, delete, replace)
return self.dp[m][n]
if __name__ == "__main__":
solver = EditDistance()
print("****************** Testing Edit Distance DP Algorithm ******************")
print()
S1 = input("Enter the first string: ").strip()
S2 = input("Enter the second string: ").strip()
print()
print(f"The minimum edit distance is: {solver.min_dist_top_down(S1, S2)}")
print(f"The minimum edit distance is: {solver.min_dist_bottom_up(S1, S2)}")
print()
print("*************** End of Testing Edit Distance DP Algorithm ***************")