View on NeetCode
View on LeetCode

Problem

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.

Solution

Approach: 2D Dynamic Programming

The key insight is that at each position, we have three choices (insert, delete, replace), and we take the minimum cost among them.

Implementation

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)

        # dp[i][j] = min operations to convert word1[0:i] to word2[0:j]
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # Base cases
        for i in range(m + 1):
            dp[i][0] = i  # Delete all characters from word1

        for j in range(n + 1):
            dp[0][j] = j  # Insert all characters from word2

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i-1] == word2[j-1]:
                    # Characters match, no operation needed
                    dp[i][j] = dp[i-1][j-1]
                else:
                    # Take minimum of:
                    # 1. Replace: dp[i-1][j-1] + 1
                    # 2. Delete from word1: dp[i-1][j] + 1
                    # 3. Insert to word1: dp[i][j-1] + 1
                    dp[i][j] = 1 + min(
                        dp[i-1][j-1],  # Replace
                        dp[i-1][j],    # Delete
                        dp[i][j-1]     # Insert
                    )

        return dp[m][n]

Approach 2: Space-Optimized 1D DP

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)

        prev = list(range(n + 1))

        for i in range(1, m + 1):
            curr = [i]  # First element is number of deletes

            for j in range(1, n + 1):
                if word1[i-1] == word2[j-1]:
                    curr.append(prev[j-1])
                else:
                    curr.append(1 + min(
                        prev[j-1],  # Replace
                        prev[j],    # Delete
                        curr[j-1]   # Insert
                    ))

            prev = curr

        return prev[n]

Approach 3: Recursion with Memoization

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        memo = {}

        def dp(i, j):
            # Base cases
            if i == 0:
                return j  # Insert all remaining chars from word2
            if j == 0:
                return i  # Delete all remaining chars from word1

            if (i, j) in memo:
                return memo[(i, j)]

            if word1[i-1] == word2[j-1]:
                result = dp(i-1, j-1)
            else:
                result = 1 + min(
                    dp(i-1, j-1),  # Replace
                    dp(i-1, j),    # Delete
                    dp(i, j-1)     # Insert
                )

            memo[(i, j)] = result
            return result

        return dp(len(word1), len(word2))

Complexity Analysis

2D DP:

• Time Complexity: O(m * n), where m and n are lengths of the two words.
• Space Complexity: O(m * n) for the dp table.

1D DP:

• Time Complexity: O(m * n).
• Space Complexity: O(n), only storing two rows.

Key Insights

1. Levenshtein Distance: This is the classic edit distance (Levenshtein distance) problem.

2. Three Operations:
   • Replace: Convert word1[i-1] to word2[j-1], cost 1 + dp[i-1][j-1]
   • Delete: Remove word1[i-1], cost 1 + dp[i-1][j]
   • Insert: Add word2[j-1], cost 1 + dp[i][j-1]

3. Character Match: When characters match, no operation needed: dp[i][j] = dp[i-1][j-1]

4. Base Cases:
   • Converting empty string to word2 requires j insertions
   • Converting word1 to empty string requires i deletions

5. Optimal Substructure: The minimum operations for full strings depends on minimum operations for prefixes.

6. Symmetry: The problem is symmetric - insert in word1 is equivalent to delete in word2 and vice versa.