Edit Distance

Edit Distance is the two-string DP interviewers use to see whether the table has really clicked. It has the same state as Longest Common Subsequence, but three choices instead of two, and edge rows that are not zero.

Once you can say which neighbouring cell each edit comes from, the code writes itself.

The problem

Given two words, return the fewest single-letter edits that turn the first into the second. An edit is one of: insert a letter, delete a letter, or replace a letter with another.

• "cart" → "cat": 1. Delete the r.
• "sunday" → "saturday": 3. Insert a, insert t, replace n with r.
• "" → "abc": 3. Three inserts.

Constraints: 0 ≤ lengths ≤ 500, lowercase English letters.

Clarifying questions

• Do all three edits cost 1? Yes. Different costs are a follow-up.
• Is swapping two neighbouring letters one edit? No — that is a different problem (Damerau distance).
• Can either word be empty? Yes. Then the answer is the other word's length.

Approach 1: the simple way — try all three edits

Walk both words from the left. If the current letters are equal, move past both for free. If not, try each edit and keep the cheapest: delete a[i] (move on in a), insert b[j] (move on in b), or replace a[i] with b[j] (move on in both).

1def edit_rec(a: str, b: str) -> int:2    """dist(i, j) = edits to turn a[i:] into b[j:]."""3    def dist(i: int, j: int) -> int:4        if i == len(a):5            return len(b) - j            # insert the rest of b6        if j == len(b):7            return len(a) - i            # delete the rest of a8        if a[i] == b[j]:9            return dist(i + 1, j + 1)    # letters agree: free10        return 1 + min(dist(i + 1, j),       # delete a[i]11                       dist(i, j + 1),       # insert b[j]12                       dist(i + 1, j + 1))   # replace a[i] with b[j]13    return dist(0, 0)

Why it is too slow. Every mismatch makes three calls. Two 6-letter words with no letter in common take 13,483 calls; 8 letters, 398,593; 10 letters, 12,146,179. At 500 letters it is hopeless. There are only (m + 1) × (n + 1) different (i, j) pairs.

The key insight

Look at the last letters of two prefixes, a[:i] and b[:j]:

• They match → nothing to do for them. dp[i][j] = dp[i − 1][j − 1].
• They differ → one edit is needed at the end, and it is one of three: - delete a[i − 1]: then turn a[:i − 1] into b[:j] → the cell above, dp[i − 1][j]. - insert b[j − 1] at the end: then turn a[:i] into b[:j − 1] → the cell to the left, dp[i][j − 1]. - replace a[i − 1] with b[j − 1]: then turn a[:i − 1] into b[:j − 1] → the diagonal, dp[i − 1][j − 1].

So dp[i][j] = 1 + min(above, left, diagonal).

The state is dp[i][j] = the fewest edits to turn the first i letters of a into the first j letters of b. The edges are not zero: dp[i][0] = i (delete all i letters) and dp[0][j] = j (insert all j letters). Getting these wrong is the most common Edit Distance bug.

Approach 2: memoisation

1from functools import cache23def edit_memo(a: str, b: str) -> int:4    @cache5    def dist(i: int, j: int) -> int:6        if i == len(a):7            return len(b) - j8        if j == len(b):9            return len(a) - i10        if a[i] == b[j]:11            return dist(i + 1, j + 1)12        return 1 + min(dist(i + 1, j), dist(i, j + 1), dist(i + 1, j + 1))13    return dist(0, 0)

O(m × n) time and space; the stack can reach m + n deep.

Approach 3: tabulation

1def edit_table(a: str, b: str) -> int:2    """dp[i][j] = fewest edits to turn a[:i] into b[:j]."""3    m, n = len(a), len(b)4    dp = [[0] * (n + 1) for _ in range(m + 1)]5    for i in range(m + 1):6        dp[i][0] = i                              # delete all i letters7    for j in range(n + 1):8        dp[0][j] = j                              # insert all j letters9    for i in range(1, m + 1):10        for j in range(1, n + 1):11            if a[i - 1] == b[j - 1]:12                dp[i][j] = dp[i - 1][j - 1]       # last letters agree: free13            else:14                dp[i][j] = 1 + min(dp[i - 1][j],      # delete15                                   dp[i][j - 1],      # insert16                                   dp[i - 1][j - 1])  # replace17    return dp[m][n]

Dry run for "cart" (rows) → "cat" (columns):

        ""  c  a  t   ""    0  1  2  3   c     1  0  1  2   a     2  1  0  1   r     3  2  1  1   t     4  3  2  1

The interesting cells:

dp[4][3] = 1: delete the r. The run of zeros from (1,1) to (2,2) is "ca" matching "ca"; the value rises only where the words part. The same table for "sunday" → "saturday" ends in 3.

Approach 4: two rows

Row i reads row i − 1 (above and diagonal) and itself (left), so two rows are enough. Remember that column 0 of row i is i, not 0.

1def min_distance(a: str, b: str) -> int:2    """Edit distance with two rows of memory."""3    n = len(b)4    prev = list(range(n + 1))                     # row 0: j inserts5    for i in range(1, len(a) + 1):6        cur = [i] + [0] * n                       # column 0: i deletes7        for j in range(1, n + 1):8            if a[i - 1] == b[j - 1]:9                cur[j] = prev[j - 1]10            else:11                cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])12        prev = cur13    return prev[n]

Complexity: O(m × n) time — 250,000 cells for two 500-letter words, a fraction of a second. O(n) space, or O(min(m, n)) if you swap the words so the shorter one runs along the row (edit distance is the same in both directions).

Edge cases

• One word empty — the edge rows give the other word's length at once.
• Equal words — the diagonal is all zeros; the answer is 0.
• No letters in common, equal lengths — every letter is replaced; the answer is the length.
• Very different lengths — at least |m − n| inserts or deletes are always needed; the table finds them.

Follow-ups

• Only insert and delete allowed — no replace, so the answer is m + n − 2 × LCS; a replace becomes one delete plus one insert.
• Are the words at most one edit apart? — no table needed: walk both with two pointers, allow one mismatch, and handle it as insert, delete or replace depending on the lengths. O(n).
• Different costs per edit — use the costs in place of the 1s; the table and order do not change.