Edit distance

You’ll recognise it when

• There are two strings and you want to know how far apart they are: typos, DNA reads, two versions of a line.
• The allowed moves are single-character edits: insert one, delete one, replace one.
• You’re asked for the fewest edits, or for the edits themselves (a diff, an alignment).
• A greedy left-to-right comparison goes wrong as soon as one insertion shifts every later letter.

Its sibling is the longest common subsequence (LCS): same table, same three neighbours, but it counts letters kept instead of edits paid for. See Variations.

The idea

You typed star and meant cart. You could fix it letter by letter from the left, but that goes wrong fast: s against c, t against a, a against r, r against t, four replacements. The cheaper fix is to see that ar is already in both. Delete the s, turn t into c, keep ar, and add a t at the end: three edits.

Finding that by hand means lining the words up cleverly. The DP instead asks a smaller question for every pair of prefixes: how many edits turn the first i letters of a into the first j letters of b? Look only at the last letter of each prefix. If they’re the same, keep it for free, and the answer is whatever the shorter prefixes cost. If they differ, the last edit was one of three things: delete a’s last letter, insert b‘s last letter, or replace one with the other. Each leaves a smaller pair of prefixes you’ve already solved, so pay 1 and take the cheapest.

How it works

Put word a down the side and word b across the top, with an extra row and column for the empty prefix, the same kind of 2-D table as in knapsack. dp[i][j] is the fewest edits that turn a[:i] into b[:j], and the answer is the bottom-right corner. The graphic fills the table for star → cart as you scroll.

Why it’s correct: any way of editing a[:i] into b[:j] ends by dealing with the last letters, and there are only four ways to do that: keep them (if equal), delete a[i-1], insert b[j-1], or replace. Each one leaves a smaller pair of prefixes, and the best way to finish that smaller job is exactly the cell above, left or diagonal. Those are filled before dp[i][j] because the table goes row by row, left to right. When the letters match, keeping them is never worse than paying for an edit, which is why the match case skips the min.

def edit_distance(a, b):
    """Fewest single-letter inserts, deletes and replacements that turn a into b."""
    n, m = len(a), len(b)
    # dp[i][j] = fewest edits that turn a[:i] into b[:j]
    dp = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = i                                   # delete all i letters
    for j in range(m + 1):
        dp[0][j] = j                                   # insert all j letters

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]            # keep it, free
            else:
                delete = dp[i - 1][j]                  # drop a[i-1]
                insert = dp[i][j - 1]                  # add b[j-1]
                replace = dp[i - 1][j - 1]             # swap the two
                dp[i][j] = 1 + min(delete, insert, replace)
    return dp[n][m]

#include <algorithm>
#include <string>
#include <vector>
using namespace std;

// Fewest single-letter inserts, deletes and replacements that turn a into b.
int editDistance(const string& a, const string& b) {
    int n = a.size(), m = b.size();
    // dp[i][j] = fewest edits that turn a[:i] into b[:j]
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 0; i <= n; i++) dp[i][0] = i;         // delete all i letters
    for (int j = 0; j <= m; j++) dp[0][j] = j;         // insert all j letters

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];           // keep it, free
            } else {
                int del = dp[i - 1][j];                // drop a[i-1]
                int ins = dp[i][j - 1];                // add b[j-1]
                int rep = dp[i - 1][j - 1];            // swap the two
                dp[i][j] = 1 + min({del, ins, rep});
            }
        }
    }
    return dp[n][m];
}

class EditDistance {
    // Fewest single-letter inserts, deletes and replacements that turn a into b.
    static int solve(String a, String b) {
        int n = a.length(), m = b.length();
        // dp[i][j] = fewest edits that turn a[:i] into b[:j]
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = i;     // delete all i letters
        for (int j = 0; j <= m; j++) dp[0][j] = j;     // insert all j letters

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];       // keep it, free
                } else {
                    int delete = dp[i - 1][j];         // drop a[i-1]
                    int insert = dp[i][j - 1];         // add b[j-1]
                    int replace = dp[i - 1][j - 1];    // swap the two
                    dp[i][j] = 1 + Math.min(delete, Math.min(insert, replace));
                }
            }
        }
        return dp[n][m];
    }
}

Row i only reads row i - 1 and the cell just to its left, so two rows are enough: O(min(n, m)) memory if you put the shorter word across the top. Like the one-row knapsack, you give up the walk back, so keep the full table when you need the edits themselves.

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):
        if a[i - 1] == b[j - 1]:
            cur[j] = prev[j - 1]
        else:
            cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
    prev = cur
# the distance is prev[-1]

Why it’s O(n·m)

The table has (n + 1) × (m + 1) cells, and each one looks at three neighbours, so time and memory are both O(n·m). The walk back takes at most n + m steps. With two rows the memory drops to O(min(n, m)); the time stays the same.

For two long strings that are almost the same, faster methods exist that only explore the cells near the diagonal, but the plain table is what interviews and most contest problems expect.

Common mistakes

dp = [[0] * (m + 1) for _ in range(n + 1)]                 # ✗ edges stay 0
for i in range(n + 1): dp[i][0] = i                         # ✓ i deletes
for j in range(m + 1): dp[0][j] = j                         # ✓ j inserts

if a[i] == b[j]:              # ✗ one letter too far
if a[i - 1] == b[j - 1]:      # ✓ the last letters of a[:i] and b[:j]

dp[i][j] = 1 + dp[i - 1][j - 1]     # ✗ pays for a letter you keep
dp[i][j] = dp[i - 1][j - 1]         # ✓ keep it for free

Variations

• Longest common subsequence. Same table, but count letters kept: on a match dp[i][j] = 1 + dp[i-1][j-1], otherwise max(dp[i-1][j], dp[i][j-1]). The edges are 0. It’s the idea behind diff: lines outside the common subsequence show up as deleted or added.
• Only insert and delete. Without replace, the distance is len(a) + len(b) - 2 · LCS: keep the common subsequence, delete the rest of a, insert the rest of b. Delete Operation for Two Strings is exactly this.
• One edit away. To check whether two strings are at most one edit apart, you don’t need the table. Walk both with two pointers; at the first mismatch, skip one letter in the longer string (or one in each if they’re the same length) and require the rest to match. O(n) time, O(1) memory.
• Weighted costs. Give each operation its own price, like a cheap replace between keys that sit next to each other on a keyboard, or a per-letter cost as in Minimum ASCII Delete Sum. Replace the three 1s with the costs; the table is unchanged.
• Spell checkers and fuzzy search. Suggest the dictionary words within distance 1 or 2 of a typo. To avoid filling a full table per word, stop a row early once every value in it exceeds the limit, or walk a trie of the dictionary and share rows between words with the same prefix.