Edit Distance

Problem

Spell checkers, DNA sequence alignment, and fuzzy search all rank how many single-character edits separate two strings. Given two words, compute the minimum number of operations - insert a character, delete a character, or replace a character - that transforms the first word into the second.

Example 1:

Input: word1 = "kitten", word2 = "sitting"
Output: 3
Explanation: kitten -> sitten (replace k with s), sitten -> sittin (replace e with i), sittin -> sitting (insert g).

Example 2:

Input: word1 = "flaw", word2 = "lawn"
Output: 2
Explanation: delete the leading f (flaw -> law), then insert n at the end (law -> lawn).

Example 3:

Input: word1 = "abc", word2 = "yabd"
Output: 2
Explanation: insert y at the front (abc -> yabc), then replace c with d (yabc -> yabd).

Constraints:

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

Solution Breakdown

Approach - two-dimensional DP over prefixes, with each allowed operation mapping to exactly one table neighbor.

Define dp[i][j] as the fewest operations turning the first i characters of word1 into the first j characters of word2. When the boundary characters match (word1[i-1] == word2[j-1]), they align for free and the diagonal carries over: dp[i][j] = dp[i-1][j-1]. When they differ, every operation on those end characters corresponds to one neighbor: replace consumes both characters for 1 + dp[i-1][j-1], delete from word1 consumes only its character for 1 + dp[i-1][j], insert into word1 supplies word2's character for 1 + dp[i][j-1] - and the cell takes the minimum of the three. The base row and column count pure insertions/deletions against an empty string. Every cell depends only on the row above and cells to its left in the current row, so two rows (prev, curr) carry the whole computation - O(n) space instead of the full O(m*n) table.

Trace "flaw" into "lawn": after the base row [0,1,2,3,4], the 'f' row mismatches everywhere and climbs to [1,1,2,3,4]; the 'l' row hits a free diagonal at 'l' ([2,1,2,3,4]); the 'a' row carries at 'a' ([3,2,1,2,3]); the 'w' row carries at 'w' ([4,3,2,2,3]) - final cell 2, realized by deleting 'f' and inserting 'n'. The "kitten"/"sitting" trace lands on 3 via two replaces and one insert; identical words carry the diagonal the whole way to 0.

Edge cases - an empty word on either side reduces the answer to the other word's length (pure inserts or deletes): "" -> "hello" is 5, "plan" -> "" is 4; identical words cost 0 with every diagonal carrying; length differences must be paid for with at least abs(m - n) inserts/deletes regardless of shared characters.

Complexity - O(m * n) time, every cell computed once at constant cost; O(n) auxiliary space for the two rolling rows (swap the words first to make n the shorter dimension when memory is tight). Operation reconstruction needs the full table retained and a backtrack from dp[m][n].