blob: a5b744f30f27a9a4ddcfb16c48ef3ad0a8cc636c (
plain) (
blame)
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
|
def print_grid(grid):
result = []
for row in grid:
result.append(" ".join(str(c) for c in row))
return print("\n".join(result))
def edit_distance(a, b):
"""
Compute the "edit distance" to transform string `a` into string `b`.
"""
grid = []
for row in range(len(a) + 1):
r = []
for col in range(len(b) + 1):
r.append(0)
grid.append(r)
# left-to-right
# populate grid[0][i]
for col in range(len(grid[0])):
grid[0][col] = col
# top-to-bottom
# populate grid[i][0]
for row in range(len(grid)):
grid[row][0] = row
for row in range(1, len(grid)):
for col in range(1, len(grid[row])):
# last characters are the same
if a[0:row][-1] == b[0:col][-1]:
grid[row][col] = grid[row - 1][col - 1]
else:
# substitution
s = 1 + grid[row - 1][col - 1]
# deletion
d = 1 + grid[row - 1][col]
# insertion
i = 1 + grid[row][col - 1]
grid[row][col] = min(s, d, i)
print_grid(grid)
return grid[-1][-1]
result = edit_distance("pizza", "pisa")
print(result)
assert result == 2
print("Success!")
|
