blob: de6c8dcef701d74be95670816725f40a711e5742 (
plain)
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
|
# Uses python3
def editDistance(A, B):
m = len(B)
n = len(A)
# Matrix = [[0 for x in range(w)] for y in range(h)]
# https://stackoverflow.com/questions/6667201/how-to-define-a-two-dimensional-array-in-python
D = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
for i in range(n + 1):
D[i][0] = i
for j in range(m + 1):
D[0][j] = j
# watch out here, range starts at 1!
for j in range(1, m + 1):
for i in range(1, n + 1):
insertion = D[i][j - 1] + 1
deletion = D[i - 1][j] + 1
match = D[i - 1][j - 1]
mismatch = D[i - 1][j - 1] + 1
if A[i - 1] == B[j - 1]:
D[i][j] = min(insertion, deletion, match)
else:
D[i][j] = min(insertion, deletion, mismatch)
return D[n][m]
if __name__ == "__main__":
print(editDistance(input(), input()))
|
