Edit Distance — The Wagner-Fischer 2D DP Algorithm Every FAANG Engineer Must Know

Problem Statement#

Given two strings word1 and word2, return the minimum number of operations required to convert word1 into word2. You have three allowed operations: Insert a character, Delete a character, or Replace a character.

Constraints:

• 0 <= word1.length, word2.length <= 500
• word1 and word2 consist of lowercase English letters

Example 1:

Input:  word1 = "horse", word2 = "ros"
Output: 3
Explanation:
  horse -> rorse (replace 'h' with 'r')
  rorse -> rose  (delete 'r')
  rose  -> ros   (delete 'e')

Example 2:

Input:  word1 = "intention", word2 = "execution"
Output: 5

Example 3:

Input:  word1 = "", word2 = "abc"
Output: 3
Explanation: Three insertions to get from empty string to "abc".

Why This Problem Matters#

Edit Distance (also called Levenshtein Distance) is one of the most practically important algorithms in computer science. It powers:

• Spell-checkers in word processors and search engines
• DNA sequence alignment in bioinformatics
• Fuzzy matching in search engines and autocomplete
• Version control diff tools (alongside LCS)
• Natural language processing for text similarity

Google, Amazon, Meta, and Microsoft ask this in senior engineering interviews to test whether candidates can handle a complex multi-case recurrence. The 2D DP table approach is the Wagner-Fischer algorithm — invented in 1974 and still optimal for general strings.

Understanding Edit Distance also unlocks the mental model for a family of sequence DP problems: wherever you align two sequences and choose between "skip from string A," "skip from string B," or "align both," the same three-case recurrence applies.

The Core Insight#

Define dp[i][j] as the minimum edit distance to convert word1[:i] into word2[:j].

Base cases:

• dp[0][j] = j — converting empty string to word2[:j] requires j insertions.
• dp[i][0] = i — converting word1[:i] to empty string requires i deletions.

Recurrence:

If word1[i-1] == word2[j-1] (current characters match — no operation needed):

dp[i][j] = dp[i-1][j-1]

If characters do not match (choose the cheapest of 3 operations):

dp[i][j] = 1 + min(
    dp[i-1][j],    # delete word1[i-1]  (move up in table)
    dp[i][j-1],    # insert word2[j-1]  (move left in table)
    dp[i-1][j-1]   # replace word1[i-1] with word2[j-1]  (diagonal)
)

Answer: dp[m][n] where m = len(word1), n = len(word2).

Intuition for the 3 operations:

• Delete word1[i-1]: After deleting, you still need to convert word1[:i-1] into word2[:j], so look at dp[i-1][j].
• Insert word2[j-1]: After inserting, you've matched word2[j-1], so still need to convert word1[:i] into word2[:j-1], so look at dp[i][j-1].
• Replace word1[i-1] with word2[j-1]: After replacing, both characters are aligned, so look at dp[i-1][j-1].

Building the DP Solution#

Step 1 — Recursive (exponential):

def minDistance(word1, word2):
    def rec(i, j):
        if i == 0: return j
        if j == 0: return i
        if word1[i-1] == word2[j-1]:
            return rec(i-1, j-1)
        return 1 + min(rec(i-1, j), rec(i, j-1), rec(i-1, j-1))
    return rec(len(word1), len(word2))

Step 2 — Memoized recursion:

from functools import lru_cache
 
def minDistance(word1, word2):
    @lru_cache(None)
    def dp(i, j):
        if i == 0: return j
        if j == 0: return i
        if word1[i-1] == word2[j-1]:
            return dp(i-1, j-1)
        return 1 + min(dp(i-1, j), dp(i, j-1), dp(i-1, j-1))
    return dp(len(word1), len(word2))

Step 3 — Bottom-up 2D tabulation:

def minDistance(word1, 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
    for j in range(n+1): dp[0][j] = j
    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], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

Step 4 — Space-optimized (1 row): Only needs the previous row and one value from the diagonal. See Optimized Solution.

Visual Dry Run#

Input: word1 = "horse", word2 = "ros"

DP table (row = word1 prefix, col = word2 prefix):

Selected cell explanations:

• dp[1][1]: 'h' != 'r' → 1 + min(dp[0][1], dp[1][0], dp[0][0]) = 1 + min(1,1,0) = 1
• dp[2][2]: 'o' == 'o' → dp[1][1] = 1
• dp[5][3]: 'e' != 's' → 1 + min(dp[4][3], dp[5][2], dp[4][2]) = 1 + min(2,4,3) = 3

Answer: dp[5][3] = 3

Optimized Solution#

Python#

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
 
        # dp[j] = edit distance between word1[:i] and word2[:j]
        # Start with the base case: converting "" to word2[:j] costs j insertions
        dp = list(range(n + 1))
 
        for i in range(1, m + 1):
            prev_row = dp[:]        # save the previous row
            dp[0] = i               # converting word1[:i] to "" costs i deletions
 
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    dp[j] = prev_row[j - 1]   # no operation needed — diagonal
                else:
                    dp[j] = 1 + min(
                        prev_row[j],     # delete word1[i-1]
                        dp[j - 1],       # insert word2[j-1]
                        prev_row[j - 1]  # replace
                    )
 
        return dp[n]

JavaScript#

var minDistance = function(word1, word2) {
    const m = word1.length;
    const n = word2.length;
 
    // Initialize dp with base case: "" -> word2[:j] costs j insertions
    let dp = Array.from({length: n + 1}, (_, j) => j);
 
    for (let i = 1; i <= m; i++) {
        const prevRow = [...dp];
        dp[0] = i;   // word1[:i] -> "" costs i deletions
 
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[j] = prevRow[j - 1];      // no operation needed
            } else {
                dp[j] = 1 + Math.min(
                    prevRow[j],              // delete
                    dp[j - 1],              // insert
                    prevRow[j - 1]          // replace
                );
            }
        }
    }
 
    return dp[n];
};

Complexity Analysis#

Common Mistakes#

1. Forgetting the empty-string base cases. dp[i][0] = i (i deletions) and dp[0][j] = j (j insertions) are non-trivial. If you initialize the entire table to 0, every cell that references the first row or column gets wrong values.

2. Missing the "no-op on match" case. When characters match, dp[i][j] = dp[i-1][j-1] with no +1. Candidates who always write 1 + min(...) get consistently wrong answers on inputs with many matching characters.

3. Getting the 3 operations confused.

• Delete word1[i-1]: look at dp[i-1][j] (you handled one fewer character from word1).
• Insert word2[j-1]: look at dp[i][j-1] (you now need one fewer character of word2).
• Replace: look at dp[i-1][j-1] (both characters handled).

Drawing arrows in the DP table helps: up = delete, left = insert, diagonal = replace or no-op.

4. Wrong diagonal in the 1D rolling approach. In the 1D rolling approach, the diagonal value is prev_row[j-1], not dp[j-1]. dp[j-1] holds the "insert" case value that was just updated this row. Using it for "replace" conflates two different operations.

5. Not handling the empty word1 or word2 edge cases. minDistance("", "abc") = 3 and minDistance("abc", "") = 3. Some implementations loop only over non-empty strings and return 0 for empty inputs — correct the base case initialization to prevent this.

Interview Tips#

• State the 3-operation semantics precisely before writing code. Draw arrows in the table to clarify: up = delete, left = insert, diagonal = replace.
• Walk through a small example. "horse" -> "ros" is the canonical example — interviewers expect you to trace it.
• Mention real-world applications early: "This is Levenshtein Distance — it powers spell-checkers and DNA alignment." Shows domain knowledge.
• Offer the 1D space optimization proactively: "I can compress from O(mn) to O(n) space by keeping only two rows." This is straightforward for Edit Distance once you see that the diagonal comes from prev_row[j-1].
• For operation reconstruction: "To trace the actual edit script, I'd save the full 2D table and backtrack from (m, n), recording which of the 3 cases each cell used."

Follow-up Questions#

Q: How do you reconstruct the actual edit operations (not just the count)? Save the full 2D table. Backtrack from (m, n): if characters matched, move diagonally; if dp[i][j] == dp[i-1][j] + 1, you deleted from word1 (move up); if dp[i][j] == dp[i][j-1] + 1, you inserted (move left); if dp[i][j] == dp[i-1][j-1] + 1, you replaced (move diagonally). Collect all operations in reverse.

Q: What if the only allowed operations are insert and delete (no replace)? This becomes the "shortest common supersequence" length problem. Without replace, edit_distance = (m - LCS) + (n - LCS) = m + n - 2 * LCS. Use LCS to find the answer.

Q: What if certain operations have different costs? Generalize the recurrence: dp[i][j] = min(dp[i-1][j] + delete_cost, dp[i][j-1] + insert_cost, dp[i-1][j-1] + replace_cost * (w1[i-1] != w2[j-1])).

Q: What is the maximum Edit Distance for strings of length m and n? max(m, n) — you delete all of word1 and insert all of word2. This is the upper bound.

Q: Can Edit Distance be solved in sub-quadratic time? For general strings, O(mn) is essentially optimal (there is a conditional lower bound under SETH). However, for strings with small edit distance k, you can solve it in O(n * k) time using the diagonal DP approach.

Key Takeaways#

• dp[i][j] = minimum edits to convert word1[:i] into word2[:j]. Base cases: dp[i][0] = i (delete all), dp[0][j] = j (insert all).
• Three cases: match (no op, take diagonal), delete (take from above dp[i-1][j]+1), insert (take from left dp[i][j-1]+1), replace (take diagonal dp[i-1][j-1]+1).
• The 1D rolling array uses prev_row[j-1] for the diagonal — this is the most common source of bugs in space-optimized implementations.
• Edit Distance is Levenshtein Distance — it powers spell-checkers, DNA alignment, autocomplete, and git diff.
• Google, Amazon, Meta, and Microsoft ask this at the hard level. Being able to explain all 3 operations with arrows in the DP table separates strong candidates from average ones.
• Reconstruction of the actual edit script requires saving the full 2D table — worth mentioning proactively in every interview.