Edit Distance: The Classic 2D String DP

You are given two words. Find the minimum number of operations to convert one word into the other. You can insert a character, delete a character, or replace a character. Each operation costs 1.

This is LeetCode 72: Edit Distance, also known as Levenshtein distance. It is one of the most classic dynamic programming problems in computer science, and it shows up constantly in interviews. If you have already worked through Longest Common Subsequence, you will recognize the structure immediately. Same 2D table, same three-neighbor dependency, just a different question being asked at each cell.

Why edit distance matters

The edit distance LeetCode problem is not just an interview favorite. It has real-world applications everywhere. Spell checkers use Levenshtein distance to suggest corrections. DNA sequence alignment is essentially edit distance with weighted operations. Fuzzy string matching in search engines, diff tools, and autocomplete systems all rely on this same idea.

In the context of interviews, edit distance is the problem that tests whether you truly understand 2D string DP. LCS asks "what is the most these strings have in common?" Edit distance asks "what is the least work to transform one into the other?" The table structure is identical, but the recurrence changes. If you can solve both, you own the entire two-string DP family.

The brute force idea

Start from the end of both strings. At each step, you have a choice:

• If the last characters match, no operation needed. Move both pointers backward.
• If they do not match, try all three operations and take the minimum:
  • Replace the last character of word1 to match word2. Both pointers move back.
  • Delete the last character of word1. Only the word1 pointer moves back.
  • Insert the last character of word2 at the end of word1. Only the word2 pointer moves back.

def min_distance_recursive(word1, word2, i, j):
    if i == 0:
        return j  # insert remaining characters of word2
    if j == 0:
        return i  # delete remaining characters of word1
    if word1[i - 1] == word2[j - 1]:
        return min_distance_recursive(word1, word2, i - 1, j - 1)
    return 1 + min(
        min_distance_recursive(word1, word2, i - 1, j - 1),  # replace
        min_distance_recursive(word1, word2, i - 1, j),       # delete
        min_distance_recursive(word1, word2, i, j - 1),       # insert
    )

This works, but it is exponential. The same (i, j) subproblem gets recomputed over and over. For strings of length m and n, the worst case is O(3^(m+n)). We need a table.

Building the 2D DP table

Define dp[i][j] as the minimum edit distance between word1[0..i-1] and word2[0..j-1]. The table has (m + 1) rows and (n + 1) columns.

The recurrence:

1. If word1[i-1] == word2[j-1], the characters match. No edit needed: dp[i][j] = dp[i-1][j-1]
2. If the characters do not match, pick the cheapest operation:
   • Replace: dp[i-1][j-1] + 1 (diagonal)
   • Delete: dp[i-1][j] + 1 (from above)
   • Insert: dp[i][j-1] + 1 (from left)
   • Take the minimum of all three.

Base cases:

• dp[0][j] = j for all j. Converting an empty string to a string of length j requires j inserts.
• dp[i][0] = i for all i. Converting a string of length i to an empty string requires i deletes.

Let's trace through word1 = "horse" and word2 = "ros":

The answer is dp[5][3] = 3. The three operations are: replace "h" with "r", delete "r" from position 2, and delete "e" from the end. (There are other valid sequences of 3 operations too.)

def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Base cases
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    # Fill the table
    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 - 1],  # replace
                    dp[i - 1][j],       # delete
                    dp[i][j - 1],       # insert
                )

    return dp[m][n]

Time: O(m * n). Every cell in the 2D table gets filled exactly once.

Space: O(m * n). The full table.

Understanding the three operations visually

Each cell dp[i][j] depends on three neighbors, and each neighbor corresponds to one of the three edit operations:

• Diagonal dp[i-1][j-1]: This is the replace operation (or a free match if the characters are equal). You are saying "I handled the first i-1 characters of word1 and the first j-1 characters of word2, and now I deal with the current pair."
• Above dp[i-1][j]: This is the delete operation. You consumed one more character from word1 (deleted it) without advancing in word2.
• Left dp[i][j-1]: This is the insert operation. You inserted a character to match word2's current character, advancing in word2 without consuming from word1.

Think of it this way: if you are standing at cell (i, j) in the table and looking backward at where you could have come from, each direction represents a different editing decision. The table finds the cheapest path from (0, 0) to (m, n).

Optimizing space to O(n)

Just like with LCS, each row only depends on the current row and the row above it. You can drop the full grid down to two rows. The one catch: when you fill dp[i][j], you need dp[i-1][j-1] (the diagonal), but that cell gets overwritten when you compute dp[i][j-1]. So you save it in a temporary variable first.

def min_distance(word1, word2):
    m, n = len(word1), len(word2)
    prev = list(range(n + 1))

    for i in range(1, m + 1):
        curr = [0] * (n + 1)
        curr[0] = i
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(
                    prev[j - 1],  # replace
                    prev[j],      # delete
                    curr[j - 1],  # insert
                )
        prev = curr

    return prev[n]

Time: O(m * n). Same.

Space: O(n). Two rows of length n + 1.

Complexity analysis

Where m = length of word1, n = length of word2.

Edge cases to watch for

• One or both strings empty: dp[0][j] = j and dp[i][0] = i. An empty word1 means you insert all of word2. An empty word2 means you delete all of word1.
• Identical strings: edit distance is 0. Every cell on the diagonal is a free match, and dp[m][n] = 0.
• Completely different strings: e.g., word1 = "abc", word2 = "xyz". Every character needs a replace, so edit distance equals max(m, n) (replace the shorter one's characters, then insert or delete the rest).
• One string is a prefix of the other: e.g., word1 = "abc", word2 = "abcdef". The edit distance is the length difference (3 inserts).
• Single character strings: word1 = "a", word2 = "b". Edit distance is 1 (one replace).

The building blocks

This problem is built on two-string-dp, the same fundamental pattern you see in Longest Common Subsequence. The structure is:

• State: dp[i][j] = minimum edit distance between word1[0..i-1] and word2[0..j-1]
• Transition: if characters match, take diagonal (free). If not, take min(diagonal, above, left) + 1.
• Base case: first row is 0, 1, 2, ... (inserts), first column is 0, 1, 2, ... (deletes)

The two-string DP pattern uses the same three-neighbor structure across many problems. What changes is the question each cell answers:

• LCS (LeetCode 1143): maximize the shared subsequence length. Match = diagonal + 1. No match = max(up, left).
• Edit Distance (LeetCode 72): minimize the transformation cost. Match = diagonal (free). No match = min(diagonal, up, left) + 1.
• Shortest Common Supersequence (LeetCode 1092): find the shortest string containing both as subsequences. Builds on LCS.
• Minimum ASCII Delete Sum (LeetCode 712): minimize the cost of deletions to make two strings equal. Same table, weighted transitions.

Once you internalize the 2D table setup, the base cases, and the three-direction dependency, you can adapt it to any of these variants by changing what each cell stores and how the recurrence combines neighbors.

From understanding to recall

You now know how to fill the edit distance DP table, why each of the three neighbors maps to an operation, and how the space optimization works. But reading through this once is not the same as writing it under pressure. In an interview, you need to set up the (m+1) x (n+1) table from memory, nail the base cases, and explain the recurrence without second-guessing whether diagonal means replace or insert.

The edit distance LeetCode problem is one of the most important problems in the two-string DP family. It shares a skeleton with LCS but adds the replace operation and switches from maximizing to minimizing. That combination of similarity and difference is exactly what trips people up. You need to drill both until the distinctions are automatic.

The two-string-dp building block is one of roughly 60 reusable patterns in the CodeBricks system. You practice each block individually with spaced repetition until writing the solution from scratch is second nature. Edit distance and LCS together form the core of the two-string comparison family, so locking them in early pays dividends across the entire DP category.

Related posts

• Longest Common Subsequence - The sister problem using the same 2D table. Maximize shared subsequence instead of minimizing edit cost.
• Word Break - String DP with a 1D table and dictionary lookups. A good companion for seeing how string DP problems differ in dimensionality.