Difficulty: Medium2-D Dynamic Programming

Edit Distance

Problem in Plain English

Given two words, find the fewest single-character insertions, deletions, or replacements that turn the first word into the second.

Problem Statement

Given two strings word1 and word2, return the minimum number of operations required to convert word1 into word2. The allowed operations are inserting a character, deleting a character, or replacing one character with another.

Each operation touches exactly one character position, and operations may be mixed freely: the classic conversion of "horse" into "ros" replaces h with r, then deletes the leftover r and e.

Return the smallest operation count over all possible conversion sequences.

Constraints

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

Examples

Example 1

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

horse -> rorse replaces h with r, rorse -> rose deletes the second r, and rose -> ros deletes e: three operations. The complete prefix table also gives a lower bound of three, so this sequence is optimal.

Example 2

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

intention -> inention deletes t, then enention, exention, and exection replace i with e and the two n letters with x and c; inserting u gives execution. These five edits attain the DP minimum.

Example 3

Input: word1 = "", word2 = "abc"
Output: 3

There are no source characters to replace or delete. Insert a, then b, then c; one insertion creates at most one needed character, so fewer than three operations cannot work.

Intuition

An edit fixes a boundary of two unmatched strings. Insert consumes a needed target character, delete consumes an unwanted source character, and replace consumes one on both sides. Equal boundary characters can align for free. For horse -> ros, replacing h, deleting the later r, and deleting e costs three. Greedy replacement alone misses cheaper alignments, so compare all smaller prefix or suffix costs.

Approaches

Recursive Try All Ops

Solution Details

Reveal Recursive Try All Ops: intuition, complexity, and code

Intuition

Let dfs(i,j) be the minimum cost to turn the remaining source suffix into the remaining target suffix. Equal leading characters align for free. On a mismatch, explicitly try inserting the target character, deleting the source character, and replacing the source character, then choose the cheapest. Repeated suffix pairs are recomputed, exposing the bottleneck that the table removes.

Step-by-Step Logic

Start at i=0, j=0 in Example 1, comparing h with r. If either suffix is empty, return the other suffix length: only insertions or deletions remain.
On equal letters advance both positions without charging an edit. Otherwise explore insert at (i,j+1), delete at (i+1,j), and replace at (i+1,j+1).
At (0,0), insertion leaves cost 3, deletion leaves cost 3, and replacement leaves cost 2. Add one to the cheapest: 1+2=3.
Follow a minimum branch to explain the result: replace h, match o, delete the later r, match s, and delete e. The exhaustive recurrence proves that no cheaper sequence exists.

Why It Works

View an edit sequence as an alignment between source and target characters: a gap on the source side is an insertion, a gap on the target side is a deletion, and a paired unequal character is a replacement. The first alignment column must be one of these three choices, reducing to exactly the suffix states the recurrence examines. On equal leading characters there is an optimal alignment pairing them for zero cost: rearranging an alignment to retain their common boundary cannot increase its cost. Thus their removal leaves the same minimum cost for the suffix pair. Empty suffixes require exactly the unmatched character count. Induction on the sum of remaining lengths proves that the minimum over all legal first columns attains the global minimum. Transposition is not an allowed operation.

Dry Run

Recursive Try All Ops: variable states at each step
State (i,j)	word1[i]	word2[j]	All dependencies / terminal rule	Return cost
(0,3)	h	end	target empty: delete 5	5
(1,3)	o	end	target empty: delete 4	4
(2,3)	r	end	target empty: delete 3	3
(4,3)	e	end	target empty: delete 1	1
(3,2)	s	s	match: (4,3) = 1	1
(3,3)	s	end	target empty: delete 2	2
(2,2)	r	s	insert (2,3)=3; delete (3,2)=1; replace (3,3)=2; 1+min=2	2
(1,2)	o	s	insert (1,3)=4; delete (2,2)=2; replace (2,3)=3; 1+min=3	3
(0,2)	h	s	insert (0,3)=5; delete (1,2)=3; replace (1,3)=4; 1+min=4	4
(1,1)	o	o	match: (2,2) = 2	2
(0,1)	h	o	insert (0,2)=4; delete (1,1)=2; replace (1,2)=3; 1+min=3	3
(5,2)	end	s	source empty: insert 1	1
(5,3)	end	end	source empty: insert 0	0
(4,2)	e	s	insert (4,3)=1; delete (5,2)=1; replace (5,3)=0; 1+min=1	1
(5,1)	end	o	source empty: insert 2	2
(4,1)	e	o	insert (4,2)=1; delete (5,1)=2; replace (5,2)=1; 1+min=2	2
(3,1)	s	o	insert (3,2)=1; delete (4,1)=2; replace (4,2)=1; 1+min=2	2
(2,0)	r	r	match: (3,1) = 2	2
(2,1)	r	o	insert (2,2)=2; delete (3,1)=2; replace (3,2)=1; 1+min=2	2
(1,0)	o	r	insert (1,1)=2; delete (2,0)=2; replace (2,1)=2; 1+min=3	3
(0,0)	h	r	insert (0,1)=3; delete (1,0)=3; replace (1,1)=2; 1+min=3	3

Complexity Analysis

Time Complexity

O(3^{m+n})

Space Complexity

O(m+n+1)

Let m and n be word lengths. Each mismatch creates three calls, each decreasing the sum of remaining lengths by at least one. O(3^(m+n)) is a loose exponential upper bound, not an exact call count; equal letters reduce branching. At most m+n+1 frames are live and only index pairs and fixed-size costs are stored: no substring allocation. The trace merges repeated uncached calls to identical states but lists every unique reached state and all dependency values. This baseline is impractical for large mismatching strings. Python temporarily reserves m+n+100 frames and restores its previous recursion limit; Java/JavaScript require adequate runtime stack capacity.

Code

Solution.java

1class Solution {2    public int minDistance(String word1, String word2) {3        return dfs(word1, word2, 0, 0);4    }5
6    private int dfs(String word1, String word2, int i, int j) {7        if (i == word1.length()) return word2.length() - j;8        if (j == word2.length()) return word1.length() - i;9        // Equal leading characters can be aligned at zero cost.10        if (word1.charAt(i) == word2.charAt(j)) {11            return dfs(word1, word2, i + 1, j + 1);12        }13        // Insert consumes only target; delete consumes only source; replace consumes both.14        int insert = dfs(word1, word2, i, j + 1);15        int delete = dfs(word1, word2, i + 1, j);16        int replace = dfs(word1, word2, i + 1, j + 1);17        return 1 + Math.min(replace, Math.min(insert, delete));18    }19}

Hints

Hint 1

Use positions or prefix lengths instead of copying shorter strings on every call. What remains when either string becomes empty?

Hint 2

A mismatch has three possible alignment columns: insert, delete, replace. Which pointer does each advance?

Hint 3

Store minimum costs for prefix pairs; row-major filling makes the above, left, and diagonal dependencies available.

Hint 4

Equal characters can align at zero extra cost, but mismatches need the minimum of all three candidates, not a greedy replacement.

Edge Cases

Two empty words require 0 operations; a single empty word requires the other word length.
Identical words require no edits, including repeated-letter words.
Insertion and deletion both matter: "a" -> "aa" and "aa" -> "a" each cost 1.
Transposing letters is not one allowed operation: "ab" -> "ba" costs 2.
Completely disjoint length-500 strings require 500 replacements; the table stays practical while the recursive branching baseline does not.

Common Mistakes and Interview Tips

Charging for matching characters makes identical words have positive distance.
Initializing empty-prefix edges with zero makes necessary insertions and deletions free.
Confusing prefix lengths with character indices causes off-by-one errors; dp[i][j] compares word1[i-1] and word2[j-1].
In suffix recursion an insertion advances only target j; a deletion advances only source i. Reversing them changes the subproblem.
Python [[0]*(n+1)]*(m+1) aliases rows; updating one cell silently changes multiple prefixes.
Greedily replacing every mismatch can miss a cheaper insertion/deletion alignment, and a transposition is never a single edit here.
The published full grid uses O((m+1)(n+1)) allocation, including empty inputs; do not describe it as constant space or claim it reconstructs the actual edits.

Key Takeaway

Sequence transformation is an alignment problem. Define a state for each pair of prefix lengths, price empty prefixes honestly, and derive each transition from the last legal edit; memoizing these overlapping states removes exponential recomputation.