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

# 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)