You can change a word with three kinds of edit: insert one character anywhere, delete one character, or replace one character with a different one.
Given word1 and word2, return the fewest edits that turn word1 into word2.
Example 1
- Input
- word1 = "sunday", word2 = "saturday"
- Output
- 3
a and t after the s, then replace the n with r.Example 2
- Input
- word1 = "", word2 = "abc"
- Output
- 3
Constraints
word1andword2each hold 0 to 500 lowercase letters.
Show the pattern
Dynamic programming (2D)
The cheapest way to turn one prefix into another builds on three slightly shorter pairs of prefixes (after an insert, a delete or a replace): a 2D table over a position in each word.
See dynamic programming (2d) in a visualiserShow the approach
Let D[i][j] be the fewest edits that turn the first i characters of word1 into the first
j characters of word2. Turning i characters into nothing takes i deletes, and building
j characters from nothing takes j inserts, which fills the first column and row.
If the last characters of the two prefixes are equal, leave them alone:
D[i][j] = D[i − 1][j − 1]. Otherwise the last edit was one of three, each costing 1:
- replace the last character:
D[i − 1][j − 1] + 1; - delete the last character of
word1's prefix:D[i − 1][j] + 1; - insert the last character of
word2's prefix:D[i][j − 1] + 1.
Take the smallest. Fill the table row by row, keeping only the previous row; the answer is the bottom-right entry.
Time: O(m × n) · Space: O(n)