Python/dynamic_programming/edit_distance.py at yash · Yashcodes04/Python · GitHub

Name: Python/dynamic_programming/edit_distance.py at yash · Yashcodes04/Python · GitHub
Rating: 4.4 (3835 reviews)
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.
"""


classEditDistance:
"""
 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:
ifm==-1:
returnn+1
elifn==-1:
returnm+1
elifself.dp[m][n] >-1:
returnself.dp[m][n]
else:
ifself.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)

returnself.dp[m][n]

defmin_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= [[-1for_inrange(len(word2))] for_inrange(len(word1))]

returnself.__min_dist_top_down_dp(len(word1) -1, len(word2) -1)

defmin_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= [[0for_inrange(n+1)] for_inrange(m+1)]

foriinrange(m+1):
forjinrange(n+1):
ifi==0: # first string is empty
self.dp[i][j] =j
elifj==0: # second string is empty
self.dp[i][j] =i
elifword1[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)
returnself.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 ***************")