Edit Distance (LeetCode 72)

The problem

Given two words a and b, return the minimum number of single-character operations needed to turn a into b. The allowed operations are insert a character, delete a character and replace a character. This is also called the Levenshtein distance.

Input:  a = "horse", b = "ros"
Output: 3

horse → rorse (replace h with r), rorse → rose (delete r), rose → ros (delete e).

How to think about it

Start with brute force. Recursively try all three operations at every mismatch. Each mismatch branches three ways, so it is roughly O(3ᵐ⁺ⁿ), and the same pair of suffixes is solved again and again.

The key insight: decide what happens to the last characters. Let dp[i][j] be the edit distance between a[:i] and b[:j]. Compare a[i-1] and b[j-1]:

• If they match, no operation is needed for them: dp[i][j] = dp[i-1][j-1].
• Otherwise pay 1 for one of three moves and take the cheapest: delete a[i-1] (dp[i-1][j]), insert b[j-1] (dp[i][j-1]) or replace one with the other (dp[i-1][j-1]). So dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).

The base cases mean “do everything”. Turning a[:i] into the empty string takes i deletes, so dp[i][0] = i. Turning the empty string into b[:j] takes j inserts, so dp[0][j] = j.

Which pattern is this? 2-D DP over two sequences, the same template as Longest Common Subsequence. The tell is “transform one string into another at minimum cost”.

Approach

1. Build a (len(a) + 1) × (len(b) + 1) table. Fill column 0 with 0, 1, …, len(a) and row 0 with 0, 1, …, len(b).
2. For each i ≥ 1 and j ≥ 1: if the characters match, copy the diagonal; otherwise take 1 plus the minimum of top, left and diagonal.
3. Return the bottom-right cell.

Solution

def edit_distance(a, b):
    dp = [[0]*(len(b)+1) for _ in range(len(a)+1)]
    for i in range(len(a)+1): dp[i][0] = i        # delete all of a[:i]
    for j in range(len(b)+1): dp[0][j] = j        # insert all of b[:j]
    for i in range(1, len(a)+1):
        for j in range(1, len(b)+1):
            if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1]          # match: free
            else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])   # delete, insert, replace
    return dp[-1][-1]
# edit_distance("horse", "ros") -> 3

Dry run

The full table for a = "horse" (rows) and b = "ros" (columns):

The bold cells are matches (o = o, s = s) that copy their diagonal. The bottom-right cell is 3.

Complexity

• Time: O(m · n). Each cell takes constant time.
• Space: O(m · n) for the table; two rows are enough if you only need the distance.

Edge cases and pitfalls

• One empty string: the answer is the other string’s length, straight from the base cases.
• Identical strings give 0.
• Mixing up insert and delete directions doesn’t change the answer (the table is symmetric in cost), but explain it consistently in an interview.
• Forgetting the base row and column (leaving them 0) undercounts every answer.

Related problems

• Longest Common Subsequence (LeetCode 1143): the same two-string table, maximising matches.
• Interleaving String (LeetCode 97): a two-string boolean DP with the same prefix-pair state.
• Regular Expression Matching (LeetCode 10): string vs pattern, filled with the same prefix-pair table.