Edit Distance

Edit Distance asks the classic question behind spell-checkers and DNA diffing: how many single-character edits turn one string into another? The answer is a textbook grid DP — fill a table where each cell reuses the answers to smaller subproblems.

The slow way first

The brute-force idea is recursion: compare the last characters. If they match, recurse on both strings minus that character. If they differ, try all three edits (insert, delete, replace) and take the cheapest, adding 1. That explores an exponential tree of choices — O(3^n) — because the same (i, j) pair is recomputed over and over.

The fix is to notice there are only (m+1) x (n+1) distinct subproblems. Store each one once.

The idea: a grid of subproblems

Define dp[i][j] = the minimum edits to turn the first i letters of word1 into the first j letters of word2. Two cases for each cell:

• Match (word1[i-1] == word2[j-1]): no edit needed, just copy the diagonal — dp[i][j] = dp[i-1][j-1].
• Mismatch: pay 1 edit plus the best neighbor — dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]), where the three neighbors are delete, insert, and replace.

The base cases anchor everything: turning an empty string into a length-j string costs j inserts (dp[0][j] = j), and turning a length-i string into empty costs i deletes (dp[i][0] = i).

Walk through it

Step through the animation. We seed the top row and left column with the base cases, then fill the interior cell by cell. Watch the match on o/o copy the diagonal for free, while mismatches pay 1 plus their cheapest neighbor. The bottom-right cell holds the final answer, 3.

Pseudocode

m, n = len(word1), len(word2)
make a (m+1) x (n+1) grid called dp
for j in 0..n: dp[0][j] = j        # empty word1 -> j inserts
for i in 0..m: dp[i][0] = i        # word2 empty -> i deletes
for i in 1..m:
    for j in 1..n:
        if word1[i-1] == word2[j-1]:
            dp[i][j] = dp[i-1][j-1]            # match: free diagonal
        else:
            dp[i][j] = 1 + min(dp[i-1][j],     # delete
                               dp[i][j-1],      # insert
                               dp[i-1][j-1])     # replace
return dp[m][n]

The Python solution

def min_distance(w1, w2):
    m, n = len(w1), len(w2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(m + 1):
        dp[i][0] = i
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if w1[i - 1] == w2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]
                )
    return dp[m][n]

• dp is a (m+1) x (n+1) grid; the extra row and column hold the empty-string base cases.
• The first two loops seed the base row (dp[0][j] = j) and base column (dp[i][0] = i).
• Inside the double loop, a match copies the diagonal dp[i-1][j-1] with no added cost.
• A mismatch pays 1 + the cheapest of the three neighbors: top (delete), left (insert), diagonal (replace).
• dp[m][n], the bottom-right cell, is the minimum edit distance for the whole strings.

Complexity

Every cell does O(1) work and there are m * n of them, so the whole table fills in O(m·n). The space can be trimmed to O(n) by keeping only the previous row, but the full grid is clearer to reason about.

When this pattern shows up

Practice