Edit Distance
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Return the minimum number of operations (insert, delete, replace a letter) to turn word1 into word2.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What does it cost to turn a word into the empty word? The empty word into a word?
- Hint 2Each of the three operations corresponds to a neighbouring table cell.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
The autocorrect on your phone turning "horse" into "ros". Table cell (a, b) = fewest edits to turn the first a letters of word1 into the first b letters of word2. Turning anything into an empty word costs deleting all letters; turning an empty word into b letters costs b insertions. If the last letters are equal, copy the diagonal. Otherwise take 1 + the cheapest of: delete (cell above), insert (cell on the left), replace (diagonal).
- The obvious way
Try all edit sequences with recursion: exponential.
- The key insight
steps[a][b] for the first a letters of word1 and first b of word2. Base: steps[a][0] = a, steps[0][b] = b. If the letters match: steps[a][b] = steps[a - 1][b - 1]. Otherwise 1 + min(steps[a - 1][b], steps[a][b - 1], steps[a - 1][b - 1]). Answer: the last cell.
- The algorithm
- Fill the first row and column with 0, 1, 2, ...
- Equal last letters: copy the diagonal.
- Else 1 + min of the three neighbours (delete, insert, replace).
- Return the bottom-right cell.
Watch it run
Exampleword1 = "horse", word2 = "ros"
Replace "h" with "r": "rorse". 1 edit.
edits: 1
Where people slip
- Do not forget the base row and column: converting to or from an empty word.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def min_distance(word1, word2):
first_length, second_length = len(word1), len(word2)
steps = [[0] * (second_length + 1) for _ in range(first_length + 1)] # edits for the first a / first b letters
for first_count in range(first_length + 1):
steps[first_count][0] = first_count # delete everything
for second_count in range(second_length + 1):
steps[0][second_count] = second_count # insert everything
for first_count in range(1, first_length + 1):
for second_count in range(1, second_length + 1):
if word1[first_count - 1] == word2[second_count - 1]:
steps[first_count][second_count] = steps[first_count - 1][second_count - 1]
else:
steps[first_count][second_count] = 1 + min(steps[first_count - 1][second_count], # delete
steps[first_count][second_count - 1], # insert
steps[first_count - 1][second_count - 1]) # replace
return steps[first_length][second_length]Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.