Edit Distance: the Levenshtein Table, Row by Row

Edit distance asks the fewest single-character edits — insert, delete or replace — that turn one string into another. Turning "horse" into "ros" takes three.

It is the archetypal two-dimensional dynamic program, and the reason it is worth working through carefully is that the recurrence is short but every term in it means something specific. Getting the meanings straight is most of the work; the code is eight lines.

Setting up the subproblem

Let d[i][j] be the edit distance between the first i characters of source and the first j characters of target. The answer is d[n][m] for the full lengths.

The base cases come free. Turning a prefix of length i into the empty string means deleting every character, so d[i][0] = i. Building a prefix of length j out of nothing means inserting every character, so d[0][j] = j. That fills the first row and the first column before any real work starts.

The recurrence, one term at a time

For every other cell there are two cases.

The characters match. If source[i-1] == target[j-1] then that character needs no edit at all, and the cost is exactly the cost of aligning everything before it: d[i][j] = d[i-1][j-1]. No plus one — this step is free.

The characters differ. One edit is unavoidable, and there are three ways to spend it. Take the cheapest:

Walking through an example

The table for "horse" → "ros". Row 0 and column 0 are the base cases.

Reading a path backwards from that corner recovers the edits: replace h with r, delete r, delete e.

The code

Written with two rows rather than the full table, because each cell reads only the row above and the cell to its left.

def edit_distance(source, target):
    # previous[j] is the distance between "" (or a shorter source prefix)
    # and the first j characters of target. The empty source costs j inserts.
    previous = list(range(len(target) + 1))

    for i, a in enumerate(source, 1):
        # Deleting i characters is the cost of turning this prefix into "".
        current = [i] + [0] * len(target)
        for j, b in enumerate(target, 1):
            if a == b:
                current[j] = previous[j - 1]          # free diagonal step
            else:
                current[j] = 1 + min(
                    previous[j - 1],                  # replace
                    previous[j],                      # delete from source
                    current[j - 1],                   # insert into source
                )
        previous = current

    return previous[len(target)]

Complexity, and why the space optimisation is safe

Every cell is computed once from three constant-time lookups, so the running time is O(n·m). That is optimal in the general case: under the strong exponential time hypothesis no algorithm computes exact edit distance in O((n·m)^(1−ε)) time, so the table is not a stepping stone to something asymptotically better.

Space is the part you can improve. The recurrence reads only row i-1 and the cell immediately left in row i. Nothing else in the table is ever consulted again, so keeping two rows is sufficient and space drops from O(n·m) to O(m). Swapping the arguments so the shorter string drives the row length makes it O(min(n, m)).

The mistakes that actually happen

• Forgetting the base row and column. A table of zeros yields 0 for every pair of strings, which looks like a subtle bug and is actually a missing initialisation.
• Adding one on a match. The diagonal step is free; adding one turns edit distance into something that counts aligned characters.
• Reading current[j] instead of previous[j] for the delete case. current[j] has not been written yet on this pass, so the value is stale from two rows ago.
• Off-by-one between string indices and table indices. The table is (n+1) x (m+1) and cell [i][j] refers to characters i-1 and j-1.