Fewest Edits Between Words
Problem
A spell checker scores how far a typed word is from a dictionary word. One edit inserts a character, deletes a character, or replaces one character with another. Given two strings a and b, return the smallest number of edits that turns a into b. Either string may be empty.
Examples
Input: a = "carpet", b = "parrot"
Output: 3
Why: replace c with p, the second p with r, and e with oInput: a = "stone", b = "notes"
Output: 4
Why: the shared letters are in a different order, so few can be keptInput: a = "", b = "abc"
Output: 3
Why: edge case, three insertsHints
0 / 3
Think about the last character of each string. Either they match, or one of the three edits must deal with at least one of them.
If the last characters match, they cost nothing and you are left with two shorter prefixes. If not, each edit also leaves you with a pair of prefixes, one shorter than before.
Fill a table where cell i, j is the fewest edits from the first i characters of a to the first j of b. Row 0 and column 0 are just counts of inserts or deletes. Any other cell copies its diagonal neighbour when the characters match, and otherwise is one plus the smallest of the diagonal, upper and left neighbours.
Solution
Let cell i, j be the fewest edits that turn the first i characters of a into the first j characters of b. When those last characters match they can be kept for free, so the cell equals the diagonal one. Otherwise the last move is a replace (diagonal), a delete from a (the cell above) or an insert of b's character (the cell to the left), each costing one. Only the previous row is needed at any time, so two rows replace the full table. Time is O(len(a) times len(b)), and space is O(len(b)).
def edit_distance(a, b):
prev = list(range(len(b) + 1)) # turning "" into each prefix of b
for i in range(1, len(a) + 1):
cur = [i] + [0] * len(b) # turning a's prefix into "" takes i deletes
for j in range(1, len(b) + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1] # matching last letters cost nothing
else: # replace, delete, insert
cur[j] = 1 + min(prev[j - 1], prev[j], cur[j - 1])
prev = cur
return prev[-1]
print(edit_distance("carpet", "parrot")) # -> 3
print(edit_distance("stone", "notes")) # -> 4
print(edit_distance("", "abc")) # -> 3Stuck on the idea rather than the code? Edit Distance covers it.