-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathstring_replace.py
More file actions
executable file
·59 lines (45 loc) · 1.36 KB
/
Copy pathstring_replace.py
File metadata and controls
executable file
·59 lines (45 loc) · 1.36 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
'''
Created on Jul 14, 2018
@author: agautam1
'''
def naiveEditDistance(str1, str2, m, n):
"""
Arguments:
str1: String 1
str2: String 2
m: length of string 1
n: length of string 2
"""
if m == 0:
return n
if n == 0:
return m
if str1[m-1] == str2[n-1]:
return naiveEditDistance(str1, str2, m-1, n-1)
return 1 + min(naiveEditDistance(str1, str2, m, n-1), #insert
naiveEditDistance(str1, str2, m-1, n-1), #replace
naiveEditDistance(str1, str2, m-1, n)) #remove
def editDistance(str1, str2, m, n):
"""
Arguments:
str1: String 1
str2: String 2
m: length of string 1
n: length of string 2
"""
dp = [[0 for x in range(n+1)] for x in range(m+1)]
for i in range(m+1):
for j in range(n+1):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif str1[i-1] == str2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = 1 + min(dp[i][j-1], #insert
dp[i-1][j-1], #replace
dp[i-1][j]) #remove
return dp[m][n]
if __name__ == '__main__':
print editDistance('ABM', 'AMZ', 3, 3)