72. Edit Distance
MediumLeetCodeGiven two strings word1
and word2
, return the minimum number of operations required to convert word1
to word2
.
You have the following three operations permitted on a word:
- Insert a character
- Delete a character
- Replace a character
Example 1
Input: word1 =
"horse"
, word2 ="ros"
Output:
3
Explanation: horse -> rorse (replace 'h' with 'r') rorse -> rose (remove 'r') rose -> ros (remove 'e')
Example 2
Input: word1 =
"intention"
, word2 ="execution"
Output:
5
Explanation: intention -> inention (remove 't') inention -> enention (replace 'i' with 'e') enention -> exention (replace 'n' with 'x') exention -> exection (replace 'n' with 'c') exection -> execution (insert 'u')
Constraints
0 <= word1.length, word2.length <= 500
word1
andword2
consist of lowercase English letters.
How to solve the problem
- Recursion with Memoization
python
# Approach 1: Recursion with Memoization
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
n, m = len(word1), len(word2)
@cache
def dfs(i: int, j: int) -> int:
# If word1 is empty, insert all characters of word2
if i < 0:
return j + 1
# If word2 is empty, delete all characters of word1
if j < 0:
return i + 1
# If current characters match, move to the previous characters
if word1[i] == word2[j]:
return dfs(i - 1, j - 1)
# Otherwise, try insert, delete, or replace, and take the minimum
return min(
dfs(i - 1, j), # delete from word1
dfs(i, j - 1), # insert into word1
dfs(i - 1, j - 1) # replace in word1
) + 1
# Start recursion from the last characters of both words
return dfs(n - 1, m - 1)
Complexity
- Approach 1 (Recursion with Memoization): Time complexity: O(n * m), Space complexity: O(n * m)
Comments
No comments yet. Be the first to comment!