Edit Distance
Problem Statement
You are given two strings word1
and word2
, each consisting of lowercase English letters.
You are allowed to perform three operations on word1
an unlimited number of times:
- Insert a character at any position
- Delete a character at any position
- Replace a character at any position
Return the minimum number of operations to make word1
equal word2
.
Example 1:
Input: word1 = "monkeys", word2 = "money"
Output: 2
Explanation:
monkeys
-> monkey
(remove s
)
monkey
-> money
(remove k
)
Example 2:
Input: word1 = "pithoncdee", word2 = "pythoncode"
Output: 3
Explanation:
pithoncdee
-> pythoncdee
(replace i
with y
)
pythoncdee
-> pythoncde
(remove last e
)
pythoncde
-> pythoncode
(insert o
)
Constraints:
0 <= word1.length, word2.length <= 100
word1
andword2
consist of lowercase English letters.
Recommended Time and Space Complexity
You should aim for a solution with O(m * n)
time and O(min(m, n))
space, where m
and n
are the lengths of word1
and word2
respectively.
Hint 1
Consider using dynamic programming to solve this problem.
Hint 2
Define dp[i][j]
as the minimum number of operations to convert word1[0...i-1]
to word2[0...j-1]
.
Hint 3
If word1[i-1] == word2[j-1]
, then dp[i][j] = dp[i-1][j-1]
.
Hint 4
Otherwise, dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
, representing deletion, insertion, and replacement, respectively.
Solution
Recursion
def min_distance_recursive(word1: str, word2: str) -> int: m, n = len(word1), len(word2)
def dfs(i, j): if i == m: return n - j if j == n: return m - i if word1[i] == word2[j]: return dfs(i + 1, j + 1) res = min(dfs(i + 1, j), dfs(i, j + 1)) res = min(res, dfs(i + 1, j + 1)) return res + 1
return dfs(0, 0)
Time complexity: O(3 ^ {m + n})
Space complexity: O(m + n)