Description
Find the minimum number of single-character insertions, deletions, and replacements needed to turn word1 into word2. Strings contain lowercase English letters and may be empty.
Solution
def min_distance(word1, word2):
dp = list(range(len(word2) + 1))
for i, a in enumerate(word1, 1):
diagonal, dp[0] = dp[0], i
for j, b in enumerate(word2, 1):
old = dp[j]
dp[j] = diagonal if a == b else 1 + min(diagonal, dp[j], dp[j - 1])
diagonal = old
return dp[-1]Examples
Example 1
- Input
["horse","ros"]- Output
3
One replacement and two deletions suffice.
Example 2
- Input
["","abc"]- Output
3
Insert all three characters.
Example 3
- Input
["same","same"]- Output
0
No edit is needed.
Approach
Use a DP row for prefix edit costs. Matching characters reuse the old diagonal; otherwise add one to the best of replacement, deletion, or insertion. Preserve the old diagonal before overwriting a cell.
Time & space
O(mn + m + n) time and O(n) auxiliary space, where m and n are word lengths.