Edit Distance Solution

Problem

Given two strings, find the minimum number of single-character operations needed to transform one string into the other. The allowed operations are: insert a character, delete a character, or replace a character with a different one.

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

Another example showing a shorter transformation:

Input: word1 = "intention", word2 = "execution"
Output: 5
Explanation: five replacements/insertions bring the strings into alignment

Intuition

The problem has optimal substructure: the minimum cost to align word1[0..i] with word2[0..j] depends only on the costs of the three smaller subproblems at (i-1, j-1), (i-1, j), and (i, j-1). When characters match, no operation is needed and we inherit the previous diagonal cost. When they differ, we take the cheapest of replace, delete, or insert and add 1. This overlapping subproblem structure makes DP the natural fit.

Approach 1 — Brute Force Recursion

Try all three operations at every mismatched position, recursing into each possibility and returning the minimum. Base cases: an empty word1 needs j insertions; an empty word2 needs i deletions.

If either string is empty, return the length of the other (pure inserts or deletes).
If the current characters match, recurse without any cost.
Otherwise, compute the cost of all three operations recursively.
Return 1 plus the minimum of the three recursive results.

1class Solution:
2    def minDistance(self, word1: str, word2: str) -> int:
3        def recurse(i: int, j: int) -> int:
4            if i == 0:
5                return j  # insert all j remaining characters of word2
6            if j == 0:
7                return i  # delete all i remaining characters of word1
8            if word1[i - 1] == word2[j - 1]:
9                return recurse(i - 1, j - 1)  # match costs nothing
10            insert_cost = recurse(i, j - 1)        # insert word2[j-1] into word1
11            delete_cost = recurse(i - 1, j)        # delete word1[i-1]
12            replace_cost = recurse(i - 1, j - 1)   # replace word1[i-1] with word2[j-1]
13            return 1 + min(insert_cost, delete_cost, replace_cost)
14
15        return recurse(len(word1), len(word2))

Time: O(3^(m+n)) — at each mismatch we branch into three independent calls with no pruning.
Space: O(m+n) — maximum recursion depth along the diagonal.

Approach 2 — Dynamic Programming

Build a 2D table bottom-up so every subproblem is solved exactly once. dp[i][j] holds the minimum operations to convert word1[0..i-1] into word2[0..j-1].

Allocate a (m+1) × (n+1) table; row 0 = j (j insertions), column 0 = i (i deletions).
For each cell (i, j), if the characters match, copy the diagonal value unchanged.
Otherwise, take the minimum of replace (dp[i-1][j-1]), delete (dp[i-1][j]), and insert (dp[i][j-1]), then add 1.
The answer is dp[m][n].

1class Solution:
2    def minDistance(self, word1: str, word2: str) -> int:
3        m, n = len(word1), len(word2)
4        dp = [[0] * (n + 1) for _ in range(m + 1)]
5
6        for i in range(m + 1):
7            dp[i][0] = i  # converting word1[0..i-1] to "" requires i deletions
8        for j in range(n + 1):
9            dp[0][j] = j  # converting "" to word2[0..j-1] requires j insertions
10
11        for i in range(1, m + 1):
12            for j in range(1, n + 1):
13                if word1[i - 1] == word2[j - 1]:
14                    dp[i][j] = dp[i - 1][j - 1]  # characters align, inherit previous cost
15                else:
16                    dp[i][j] = 1 + min(
17                        dp[i - 1][j - 1],  # replace word1[i-1] with word2[j-1]
18                        dp[i - 1][j],      # delete word1[i-1] (row shrinks, col stays)
19                        dp[i][j - 1],      # insert word2[j-1] (col shrinks, row stays)
20                    )
21
22        return dp[m][n]

Time: O(m × n) — every cell is filled exactly once.
Space: O(m × n) — the full 2D table; reducible to O(n) with a rolling array.

Complexity Summary

Approach	Time	Space	When to use
Brute Force Recursion	O(3^(m+n))	O(m+n)	Only for understanding the recurrence; never for real inputs
Dynamic Programming	O(m × n)	O(m × n)	All practical cases; optimize to O(n) space if memory is tight

Common Mistakes

Getting insert and delete cells backwards: dp[i-1][j] is a deletion (word1 loses a character, word2 stays), while dp[i][j-1] is an insertion (word2 loses a character, word1 stays). Swapping them still passes most tests because delete and insert are symmetric — the table value is unchanged, but the interpretation of which operation was chosen is wrong.
Off-by-one when indexing into the strings: The table is (m+1) × (n+1) so dp[i][j] corresponds to word1[i-1] and word2[j-1]. Using word1[i] directly causes an out-of-bounds error when i == m.
Skipping the base case initialization: Without setting dp[i][0] = i and dp[0][j] = j before the nested loops, those cells remain 0 and every cell in the first row and column will compute incorrectly.
Applying the match shortcut when characters differ: When word1[i-1] == word2[j-1] the cost is dp[i-1][j-1] (no operation). When they differ, replace costs dp[i-1][j-1] + 1 — both branches reference the diagonal, but only the mismatch branch adds 1. Forgetting the +1 for replace produces values that are too small.
Exponential brute force on moderately long strings: The recursive solution without memoization recomputes the same (i, j) state from many call paths. Even for strings of length 20, the call tree has millions of nodes — always add a cache or switch to the DP table.

Edit Distance — Solution