algoadvance

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:

1. Insert a character
2. Delete a character
3. Replace a character

Clarifying Questions

1. Case Sensitivity: Are the strings case-sensitive? (Assuming yes unless stated otherwise)
2. Empty Input: Can the input strings be empty?
3. Constraints: What are the length constraints on the input strings? (Typically handled in LeetCode constraints)

Example

Input: word1 = "horse", word2 = "ros"
Output: 3
Explanation:
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')

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

Strategy

We will use dynamic programming (DP) to solve this problem. We can create a 2D DP table where dp[i][j] represents the minimum edit distance between the first i characters of word1 and the first j characters of word2.

Steps:

1. Initialize a 2D list dp with dimensions (len(word1) + 1) x (len(word2) + 1).
2. Fill the first row and the first column based on the edge cases:
   • dp[0][j] = j: Transforming an empty string to the first j characters of word2.
   • dp[i][0] = i: Transforming the first i characters of word1 to an empty string.
3. Populate the DP array by considering the three operations:
   • insert = dp[i][j-1] + 1
   • delete = dp[i-1][j] + 1
   • replace = dp[i-1][j-1] if word1[i-1] == word2[j-1], otherwise dp[i-1][j-1] + 1
4. The value at dp[len(word1)][len(word2)] will give the minimum number of operations required.

Code

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    
    # Create a DP table to save minimum edit distances
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # Initialize the first row and column of the DP table
    for i in range(1, m + 1):
        dp[i][0] = i
    for j in range(1, n + 1):
        dp[0][j] = j
    
    # Fill the DP table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(
                    dp[i - 1][j] + 1,    # Delete
                    dp[i][j - 1] + 1,    # Insert
                    dp[i - 1][j - 1] + 1 # Replace
                )
    
    return dp[m][n]

# Example usage
print(minDistance("horse", "ros")) # Output: 3
print(minDistance("intention", "execution")) # Output: 5

Time Complexity

• Time Complexity: O(m * n), where m is the length of word1 and n is the length of word2. This is because we are filling a 2D DP table of size (m+1) x (n+1).

• Space Complexity: O(m * n) for the same reason, the space required to store the DP table.

This solution efficiently computes the minimum edit distance using dynamic programming.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?