AI Hints
Home›DSA in Python Tutorial›More Dynamic Programming
DSA in Python · Lesson 96 of 132

Practice: Edit Distance

How spell checkers think.

⏱ 2 min read▶ Video at 1:54:54🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

When you type kitten, but meant sitting, how far off were you? Edit distance counts the fewest single letter changes needed. Insert a letter, delete a letter, or swap one letter for another. Spell checkers use it to suggest corrections.

Practice: Edit Distance
From the video: Practice: Edit Distance
  • kitten → sitting
  • Fewest single letter edits
  • Insert, delete, or replace

A grid of edits

Like the common subsequence, we fill a grid. The first row and column count edits from an empty word. If two letters match, no edit is needed, so we copy the diagonal. Otherwise, it's one, plus the cheapest of delete, insert, or replace. Run it. Kitten to sitting takes three edits.

edit.pypython
def edit_distance(a, b):
    d = [[i + j if i * j == 0 else 0 for j in range(len(b) + 1)] for i in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                d[i][j] = d[i - 1][j - 1]
            else:
                d[i][j] = 1 + min(d[i - 1][j], d[i][j - 1], d[i - 1][j - 1])
    return d[-1][-1]

for a, b in [("kitten", "sitting"), ("flaw", "lawn"), ("same", "same")]:
    print(a, "->", b, edit_distance(a, b))
Output
kitten -> sitting 3
flaw -> lawn 2
same -> same 0

Suggesting corrections

A spell checker compares the word you typed with real words, and suggests the ones with the smallest edit distance. Kitten to sitting is three. Replace K with S, replace E with I, and add a G. The same algorithm compares DNA, and powers fuzzy search.

keyvalue
Deletecell above + 1
Insertcell left + 1
Replacediagonal + 1
Matchdiagonal, free

Summary

Edit distance fills a grid, choosing the cheapest of insert, delete, or replace. That's the end of dynamic programming. Next, backtracking, for exploring every possibility.

Key takeaways
  • Grid of prefixes
  • Match is free
  • 1 + cheapest edit
Next up: Backtracking — try, and undo