Skip to content

72. Edit Distance

MediumLeetCode

Given 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 and word2 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!