Edit Distance: The Capstone Two-String DP

This one is a Medium-rated classic reported from Google, Amazon, Microsoft interviews: "Edit Distance". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Dynamic Programming pattern on sight. Part 11 of 11 in the Dynamic Programming arc.

The Problem

Given two words, return the minimum operations — insert, delete, or replace a character — to convert one into the other. Levenshtein distance: the capstone of the two-sequence DP family, powering spell-checkers, fuzzy search, and bioinformatics, and a Google favorite for two decades.

Input:  word1 = "horse", word2 = "ros"
Output: 3
horse -> rorse (replace) -> rose (delete) -> ros (delete).

Recognizing the Dynamic Programming Pattern

Dynamic programming is recursion with the repetition removed: define the answer to a subproblem, express it in terms of smaller subproblems, and compute each exactly once — top-down with memoization or bottom-up with a table. In interviews the grade hinges on the state definition said out loud ('dp[i] is the best answer using the first i items') far more than on the loop that follows. Most FAANG DP questions are one-dimensional or a small 2D grid — the nine below cover the shapes that repeat.

Transform prefix to prefix with local operations: dp[i][j], the cost for the first i characters of one word against the first j of the other. Equal last characters ride the diagonal free; otherwise one plus the min over the three neighbors — each neighbor is one operation, and mapping them correctly is the understanding being tested.

The Approach

Padded table with base rows equal to i and j (pure deletions or insertions). Fill row-major: match copies the diagonal; mismatch takes 1 + min(delete = up, insert = left, replace = diagonal).

Narrate the neighbor-to-operation mapping once, precisely — it is the difference between reciting the recurrence and owning it. Rolling-row compression to O(n) applies as in LCS; reconstruction of the operation sequence needs the full table.

Python Solution

def min_distance(word1: str, word2: str) -> int:
    """Levenshtein distance between word1 and word2."""
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i                   # delete everything
    for j in range(n + 1):
        dp[0][j] = j                   # insert everything
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # delete from word1
                    dp[i][j - 1],      # insert into word1
                    dp[i - 1][j - 1],  # replace
                )
    return dp[m][n]

Complexity

• Time: O(m·n) — constant work per prefix pair
• Space: O(m·n) — full table (O(min(m, n)) rolling if only the distance is needed)

Interview Tips and Follow-Ups

• One Edit Distance (is the distance exactly 1?) deserves O(n) two pointers, not this table — matching solution size to question size is its own signal.
• Weighted operations (replace costs 2, as in some Amazon variants) change only the constants in the min — the table survives; say so.
• This closes the series' DP arc: LCS, Edit Distance, and subset-sum are the three tables from which most interview DP is assembled. Master the trio, improvise the rest.

That wraps part 11 of the Dynamic Programming arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.