How do you compute the edit distance between two strings?
You build a table where each entry is the number of changes you need to turn one part of a string into the other part.
def edit_distance(a, b):
rows, cols = len(a), len(b)
table = [[0] * (cols + 1) for _ in range(rows + 1)]
for i in range(rows + 1):
table[i][0] = i
for j in range(cols + 1):
table[0][j] = j
for i in range(1, rows + 1):
for j in range(1, cols + 1):
if a[i - 1] == b[j - 1]:
table[i][j] = table[i - 1][j - 1]
else:
table[i][j] = 1 + min(
table[i - 1][j],
table[i][j - 1],
table[i - 1][j - 1],
)
return table[rows][cols]
So how does it work? The first row and the first column are the easy cases. To turn an empty string into the first j characters of the second string you need j insertions, and to turn the first i characters of the first string into an empty string you need i deletions.
And then at each cell there are two cases. If the two characters are the same then no change is needed and you take the entry above and to the left. If they are different then you need one change, and you have three choices.
the choice what it does the entry
---------------- ---------------------- -------------------
delete throw away a character the entry above
insert add a character the entry to the left
replace change a character the entry above and left
And you take the smallest of the three and add one for the change itself.
the strings "horse" and "ros"
the table
"" r o s
"" 0 1 2 3
h 1 1 2 3
o 2 2 1 2
r 3 2 2 2
s 4 3 3 2
e 5 4 4 3
the answer is 3
And the complexity is O of the length of a times the length of b for the time, and the same for the space.
So the rule to remember is this. Three choices when the characters differ, and the smallest one wins.
The next two questions in this topic show the full table version and the version that uses two rows.