Edit DistanceEdit distance

01Why it exists

Reach for it when you see:How similar two strings are, the fewest steps turning A into B, insert / delete / replace, spelling correction, fuzzy matching, error-tolerant search, word error rate, a dp[i][j] over two prefixes.

02The core idea

Edit distance (the Levenshtein distance) is the fewest operations needed to turn string A into string B, with three operations allowed: insert a character, delete a character, or replace one character with another. The state is the same pair of prefixes as in LCS: dp[i][j] is the fewest steps that turn A's first i characters into B's first j. The boundary is as plain as it gets — dp[i][0] = i (delete everything) and dp[0][j] = j (insert everything) — and the answer sits in dp[m][n].

The transition, once again, looks only at the last character. If A[i−1] = B[j−1], those two characters line up as they are and dp[i][j] = dp[i−1][j−1], at no cost. If they differ, then in any optimal set of operations A's last character meets one of exactly three fates: it is replaced by B's last character (the diagonal, dp[i−1][j−1] + 1), it is deleted (above, dp[i−1][j] + 1), or it stays and B's last character was inserted (the left, dp[i][j−1] + 1). Those three cover every possibility, so the smallest of them is the answer. The table is filled row by row, left to right, exactly as in LCS.

The cost is O(mn) time. Recovering the sequence of operations needs the whole table, O(mn), after which you walk back from the bottom-right corner, checking at each cell which of the terms produced it. When only the distance matters, each row depends on nothing but the row above — except that the transition reads the diagonal, so it has to be saved in a variable before being overwritten — and the space falls to O(min(m, n)). In practice the real question is often just whether the distance is at most k; spelling suggestions, for instance, care only about words within one or two steps. Any path of distance ≤ k stays inside the band where |i − j| ≤ k, so computing that band alone is O(k·n), and candidates whose lengths already differ by more than k can be skipped without computing anything.

The usual traps: adding 1 even when the characters match; forgetting to initialise row 0 and column 0 to 0..n and 0..m; and treating a swap of two adjacent characters as one step, when under the Levenshtein distance teh → the really does cost two replacements. Counting it as one means moving to the Damerau distance, which adds a transposition operation. Nor do the three operations have to cost the same: OCR and speech pipelines often make particular replacements cheaper, and the transition still holds, with the +1 replaced by each operation's own cost. How this relates to the previous lesson: drop the replace operation and allow only insertions and deletions, and the answer becomes m + n − 2·LCS. The same two-prefix table also shows up in Interleaving String, Distinct Subsequences and wildcard matching.

03The algorithm

1. 1Allocate an (m+1) × (n+1) table with dp[i][0] = i and dp[0][j] = j.
2. 2Fill it row by row, left to right: if A[i−1] == B[j−1] then dp[i][j] = dp[i−1][j−1], otherwise 1 + min(diagonal, above, left), which stand for replace, delete and insert respectively.
3. 3dp[m][n] is the edit distance.
4. 4For the sequence of operations: walk back from (m, n), see which source this cell equals once that step's cost is added, move there and record the operation, then reverse the list once you reach (0, 0).
5. 5When only the distance matters, roll a single row and stash the diagonal; when the question is only "is it ≤ k", compute nothing but the band where |i − j| ≤ k.

04Interactive demo

Turning horse into ros, the example from LeetCode 72. Row 0 and column 0 go in first, then the cells one at a time: blue is the cell being filled, amber is the source it ends up using, and the small arrow in the corner of a cell records which direction that source came from (↖ match or replace, ↑ delete, ← insert; when several sources tie, the pick order is replace, delete, insert). Once the table is full the trace back starts at the bottom-right corner, green marks the path, and the operations appear on the right in order: replace h → r, delete r, delete e. Three steps, exactly the value in the bottom-right cell.

05Code

Python has the full table, the recovery of the operation sequence, and the space-saving version that rolls a single row, finishing with a spelling suggestion for teh that shows a swap of two characters costing two steps under the Levenshtein distance. C++ has the version built on one row plus a single diagonal variable, and the one that computes only the band in order to decide whether the distance is at most k.

def edit_table(a, b):
    """dp[i][j]: fewest insertions, deletions or replacements turning a's first i characters into b's first j"""
    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                               # into the empty string: i deletions
    for j in range(n + 1):
        dp[0][j] = j                               # out of the empty string: j insertions
    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]        # last characters match, nothing to do
            else:
                dp[i][j] = 1 + min(dp[i - 1][j - 1],   # replace a[i-1] → b[j-1]
                                   dp[i - 1][j],       # delete a[i-1]
                                   dp[i][j - 1])       # insert b[j-1]
    return dp


def edit_script(a, b):
    """Walk back from the bottom-right corner to recover the operations (ties: replace, then delete, then insert)"""
    dp = edit_table(a, b)
    i, j, ops = len(a), len(b), []
    while i > 0 or j > 0:
        if i > 0 and j > 0 and a[i - 1] == b[j - 1]:
            i, j = i - 1, j - 1                    # a match, so it costs no step
        elif i > 0 and j > 0 and dp[i][j] == dp[i - 1][j - 1] + 1:
            ops.append(f"replace {a[i - 1]}→{b[j - 1]}")
            i, j = i - 1, j - 1
        elif i > 0 and dp[i][j] == dp[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_distance(a, b):
    """Distance only: roll a single row. The diagonal cur[j] needs is exactly prev[j-1]"""
    prev = list(range(len(b) + 1))
    for i, ca in enumerate(a, 1):
        cur = [i] + [0] * len(b)
        for j, cb in enumerate(b, 1):
            cur[j] = prev[j - 1] if ca == cb else 1 + min(prev[j - 1], prev[j], cur[j - 1])
        prev = cur
    return prev[-1]


if __name__ == "__main__":
    print(edit_table("horse", "ros")[-1][-1], edit_script("horse", "ros"))
    # 3 ['replace h→r', 'delete r', 'delete e'] (the same as the demo)
    print(edit_distance("intention", "execution"), edit_distance("recieve", "receive"))   # 5 2
    words = ["the", "ten", "tea", "eh", "tech", "then"]
    print(sorted(words, key=lambda w: (edit_distance("teh", w), w)))
    # ['eh', 'tea', 'tech', 'ten', 'the', 'then']: "the" takes 2 steps, because swapping two characters counts as two replacements

06Practice

• LeetCode 72Edit DistanceMedium
• LeetCode 97Interleaving String (another table over two prefixes)Medium
• LeetCode 115Distinct Subsequences (swap "fewest steps" for "how many ways")Hard
• LeetCode 44Wildcard Matching (* can absorb any length)Hard
• LeetCode 1312Minimum Insertion Steps to Make a String Palindrome (compare the string with its reverse)Hard