The problem
Return the fewest operations that turn word1 into word2, where an operation inserts a character, deletes a character, or replaces one character with another.
Examples
01
- Input
word1 = "horse", word2 = "ros"
- Output
3
02
- Input
word1 = "intention", word2 = "execution"
- Output
5
Constraints
- 0 ≤ word1.length, word2.length ≤ 500
- Only lowercase English letters.
The idea
Let d(i, j) be the edits turning the first i letters of word1 into the first j of word2. Turning into or from an empty word takes j inserts or i deletes. If the last letters match, they cost nothing: d(i − 1, j − 1).
Otherwise the last step was one of three: delete word1’s last letter (d(i − 1, j)), insert word2’s last letter (d(i, j − 1)), or replace one with the other (d(i − 1, j − 1)) — 1 plus the cheapest. For horse → ros the table ends at 3: replace h with r, delete r, delete e.
- Time
- O(m · n)
- Space
- O(n) — one row
Solution · every language run against every case
class Solution: def minDistance(self, word1: str, word2: str) -> int: # d(i, j): edits turning word1[:i] into word2[:j]. If the last letters match, d(i-1, j-1); # otherwise 1 + the cheapest of delete d(i-1, j), insert d(i, j-1), replace d(i-1, j-1). row = list(range(len(word2) + 1)) # from the empty word: j inserts for i in range(1, len(word1) + 1): diag, row[0] = row[0], i # into the empty word: i deletes for j in range(1, len(word2) + 1): above = row[j] if word1[i - 1] == word2[j - 1]: row[j] = diag else: row[j] = 1 + min(above, row[j - 1], diag) diag = above return row[-1]