Edit Distance Explained: The DP Table, Cell by Cell

Edit distance is the smallest number of single-character inserts, deletes and replacements that turn one string into another. The recurrence is three lines long, and most people can recite it. Fewer can say what a single cell of the table means, which is exactly what you need when the interviewer asks for the actual edits rather than the number.

This article builds the table from that meaning, walks it back to recover the edits, shrinks it to two rows, and checks every answer against a search that knows nothing about tables.

The problem it solves

Given two words, how far apart are they? "Far" here means edits: flaw becomes lawn by deleting the f and appending an n, so the distance is 2. The measure is often called Levenshtein distance.

It is the score behind spelling suggestions, fuzzy search, and diffing short strings. It is also the cleanest example of a two-string dynamic programme, and the same table shape reappears in longest common subsequence and sequence alignment.

Brute force is hopeless. Every position can be kept, deleted, replaced, or have something inserted before it, so the number of edit sequences explodes with length. The table exists to stop re-solving the same smaller question.

The intuition

Name the smaller question precisely. Let d[i][j] be the edit distance between the first i characters of a and the first j characters of b. The answer is the bottom-right cell, d[len(a)][len(b)].

The edges are free to fill. Turning a prefix of length i into the empty string takes i deletes, so d[i][0] = i. Building a prefix of length j from nothing takes j inserts, so d[0][j] = j.

For every other cell, look at the last character of each prefix. There are only three things the cheapest edit script can do with them:

• Delete the last character of a's prefix. Then you still owe d[i - 1][j], plus one.
• Insert the last character of b's prefix at the end. You still owe d[i][j - 1], plus one.
• Replace one with the other. You owe d[i - 1][j - 1], plus one — or plus zero if the two characters are already equal.

That last case is the one people blur. When a[i - 1] == b[j - 1] there is nothing to edit, so the cell copies its diagonal neighbour unchanged. It is not "the minimum of three plus one"; it is free.

Each cell therefore depends only on the cell above, the cell to the left and the cell diagonally up-left. Fill row by row and all three are always ready.

Watch it run

The animation turns flaw into lawn. Row 0 and column 0 are filled first. Then each cell lights the neighbour it copied from: a green arrow for a free diagonal when the letters match, an amber one when an edit was paid for. Watch the l, a and w matches carry the cost diagonally down the table, and the corner settle at 2.

The code

The full table, a walk back from the corner that recovers the edits, and the two-row version you would use when only the number matters:

def edit_table(a, b):
    rows, cols = len(a) + 1, len(b) + 1
    d = [[0] * cols for _ in range(rows)]
    for i in range(rows):
        d[i][0] = i                     # delete all of a[:i]
    for j in range(cols):
        d[0][j] = j                     # insert all of b[:j]
    for i in range(1, rows):
        for j in range(1, cols):
            if a[i - 1] == b[j - 1]:
                d[i][j] = d[i - 1][j - 1]           # free: copy the diagonal
            else:
                d[i][j] = 1 + min(d[i - 1][j],      # delete a[i-1]
                                  d[i][j - 1],      # insert b[j-1]
                                  d[i - 1][j - 1])  # replace
    return d

def edit_script(a, b):
    d, i, j, ops = edit_table(a, b), len(a), len(b), []
    while i or j:                       # walk back from the corner
        if i and j and a[i - 1] == b[j - 1] and d[i][j] == d[i - 1][j - 1]:
            i, j = i - 1, j - 1
        elif i and j and d[i][j] == d[i - 1][j - 1] + 1:
            ops.append(f"replace {a[i - 1]}->{b[j - 1]}"); i, j = i - 1, j - 1
        elif i and d[i][j] == d[i - 1][j] + 1:
            ops.append(f"delete {a[i - 1]}"); i -= 1
        else:
            ops.append(f"insert {b[j - 1]}"); j -= 1
    return ops[::-1]

def edit_two_rows(a, b):
    prev = list(range(len(b) + 1))
    for i in range(1, len(a) + 1):
        cur = [i] + [0] * len(b)
        for j in range(1, len(b) + 1):
            same = a[i - 1] == b[j - 1]
            cur[j] = prev[j - 1] if same else 1 + min(prev[j], cur[j - 1], prev[j - 1])
        prev = cur
    return prev[-1]

print(edit_table("flaw", "lawn")[-1][-1])       # 2
print(edit_script("flaw", "lawn"))              # ['delete f', 'insert n']
print(edit_two_rows("kitten", "sitting"))       # 3
print(edit_script("kitten", "sitting"))         # ['replace k->s', 'replace e->i', 'insert g']

The walk back works because every cell remembers, implicitly, which neighbour it came from: whichever one it equals after undoing the step's cost. Any neighbour that satisfies the equation leads to an optimal script, which is why two correct programs can print different edits with the same length.

To make sure the recurrence is right, compare it with something that uses no recurrence at all. Treat every string as a node, every single edit as an edge, and run a breadth-first search from a until it reaches b. The first time BFS arrives is the true distance:

import random
from collections import deque

def edit_bfs(a, b):                     # shortest path through actual strings
    alphabet = set(a + b)
    seen, queue = {a: 0}, deque([a])
    while queue:
        s = queue.popleft()
        if s == b:
            return seen[s]
        nxt = [s[:k] + s[k + 1:] for k in range(len(s))]
        nxt += [s[:k] + c + s[k:] for k in range(len(s) + 1) for c in alphabet]
        nxt += [s[:k] + c + s[k + 1:] for k in range(len(s)) for c in alphabet]
        for t in nxt:
            if t not in seen and len(t) <= max(len(a), len(b)):
                seen[t] = seen[s] + 1
                queue.append(t)

random.seed(8)
ok = True
for _ in range(1500):
    a = "".join(random.choice("abc") for _ in range(random.randint(0, 5)))
    b = "".join(random.choice("abc") for _ in range(random.randint(0, 5)))
    dist = edit_bfs(a, b)
    ok &= edit_table(a, b)[-1][-1] == dist == edit_two_rows(a, b)
    ok &= len(edit_script(a, b)) == dist
print(ok)                               # True

Limiting BFS to letters already present and to strings no longer than the longer input is safe: an optimal script can always do its deletes first and its inserts last, so it never needs a longer detour or a foreign letter.

The complexity

There are (m + 1) × (n + 1) cells and each costs constant work, so time is O(m × n). The full table is also O(m × n) memory, which you need if you want the edits back. For the number alone, each row reads only the row above, so two rows suffice: O(min(m, n)) memory if you put the shorter string along the columns.

Where it goes wrong

• Adding one on a match. The diagonal is free when the characters agree. Charging for it inflates every answer on similar strings.
• Forgetting the edges. Initialising row 0 and column 0 to zero says an empty string is already equal to everything, and the corner comes out too small.
• Off-by-one indexing. Cell d[i][j] compares a[i - 1] with b[j - 1]. The table is one larger than the strings in each direction.
• Overwriting the diagonal in the two-row version. With a single row updated in place, prev[j - 1] has already been replaced by the time you need it. Keep two rows, or save the diagonal in a variable before overwriting.

For the sibling problem that scores matches instead of edits, see longest common subsequence.

How to say it in an interview

"Let d[i][j] be the distance between the first i characters of one word and the first j of the other. The first row and column are just counts of inserts or deletes. For any other cell I look at the last characters: if they match, I copy the diagonal; if not, I take one plus the cheapest of delete, insert and replace. That's O(m × n) time, and two rows of memory if I only need the number."

Then offer the walk back unprompted. Saying "I keep the full table if you want the edits, and here's how I recover them" turns a memorised recurrence into an explanation.