Lesson 53 — DP VII: edit distance

~25 minutes · Day 69 · two-string DP · Python

Tonight's interview pattern is what lets a spellchecker, diff tool, or search box ask: “how far apart are these two words?” The LeetCode version is Edit Distance: find the fewest insert, delete, or replace operations needed to turn one word into another. The classic name is Levenshtein distance, the minimum number of one-character edits between two strings (Wikipedia).

The invariant

Memorize this line

dp[i][j] = edits to turn one prefix into the other: free when characters match, else 1 + min(insert, delete, replace).

That one sentence is the whole solution. The table cell is not about the whole words yet. It is about two prefixes: word1[:i] and word2[:j]. Small prefixes build larger prefixes.

The table shape

Put prefixes of the first word down the side and prefixes of the second word across the top. Each cell only needs three earlier cells: left, up, and diagonal.

Edit distance DP transition A DP table cell receives arrows from its left, upper, and diagonal neighbors, labeled insert, delete, and replace or match. word2 prefixes word1 prefixes "" r o s "" h o r diag up left dp[i][j] delete from word1 insert into word1 replace, or match for free if mismatch: 1 + min(left, up, diag)

Edit Distance: the slow way first

The brute force idea is honest: compare the last characters of the two remaining prefixes. If they match, move diagonally for free. If they do not, try all three edits and take the cheapest result. That recursion is exponential, up to O(3m+n), because the same prefix pair gets recomputed many times.

def slow(i, j):
    if i == 0: return j              # insert j chars
    if j == 0: return i              # delete i chars
    if word1[i - 1] == word2[j - 1]:
        return slow(i - 1, j - 1)    # matching char is free
    return 1 + min(
        slow(i, j - 1),              # insert
        slow(i - 1, j),              # delete
        slow(i - 1, j - 1)           # replace
    )

The fix is not a new idea. Keep the same meaning, but store each prefix answer once.

Edit Distance: the DP way

LeetCode 72 asks for the minimum number of insertions, deletions, and replacements (problem statement). The base row and base column are the cost of converting a word into the empty string, or the empty string into a word.

def min_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1): dp[i][0] = i       # delete all i chars
    for j in range(n + 1): dp[0][j] = j       # insert all j chars
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]  # match is free
            else:
                dp[i][j] = 1 + min(dp[i][j - 1], dp[i - 1][j], dp[i - 1][j - 1])
    return dp[m][n]

Read the mismatch line slowly: left means insert, up means delete, diagonal means replace. They are all one edit plus a smaller solved prefix pair.

Transfer: same table, fewer moves

Delete Operation for Two Strings: find the minimum deletions needed to make two strings equal.

Before opening the reveal: keep the same state, dp[i][j]. If the current characters match, what should happen? If they do not match, which moves are still legal?

Your prediction first - then reveal.

Same state: dp[i][j] is the minimum deletions to make word1[:i] and word2[:j] equal. Match means copy the diagonal. Mismatch means delete one current character from either side: 1 + min(dp[i - 1][j], dp[i][j - 1]). The replace move disappears.

What the trade buys you

ApproachTimeSpace
Brute force recursionO(3m+n)O(m+n)
2-D DP tableO(mn)O(mn)

The DP table is the price of not forgetting. Every prefix pair is solved once, then reused.

Practice - answer before you scroll past

1. What does dp[i][j] mean here?

2. If the two current characters match, which value can you copy?

3. Spot the bug in this match case:

if a[i - 1] == b[j - 1]:
    dp[i][j] = 0

4. Which new problem has the same two-string DP shape?

Your move (tonight)

Solve Edit Distance in your Notion tracker with the cycle - predict → attempt → compare → encode:

  1. Predict: state the prefix meaning, the three mismatch moves, the base row, and the answer cell.
  2. Attempt: write the bottom-up table without watching anything first.
  3. Compare: watch the primary source below and find the first sentence where his reasoning differs from yours.
  4. Encode: write the invariant from this page in your own words.
One primary source

Watch NeetCode - Edit Distance after your attempt, as the compare step. Do not start there; use it to repair your model.

Stuck or curious? Ask your teacher (the agent) - that's what it's for.