LeetCode 72: Edit Distance

Problem Description

LeetCode Problem 72

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.

Difficulty: Medium

Tags: string, dynamic programming

Rating: 98.38%

Understanding the Solution

Example Walkthrough

Let’s take the first example where:

• word1 = “horse”
• word2 = “ros”

We’ll use a 2D array (matrix) where:

• Rows represent characters from word1 (“horse”)
• Columns represent characters from word2 (“ros”)
• Each cell [i][j] represents the minimum operations needed to transform word1[0…i] to word2[0…j]

Here’s how our DP table looks initially (with base cases filled):

    ''  r   o   s
''  0   1   2   3
h   1   ?   ?   ?
o   2   ?   ?   ?
r   3   ?   ?   ?
s   4   ?   ?   ?
e   5   ?   ?   ?

Base Cases

1. First row (empty string to word2): number of insertions needed
2. First column (word1 to empty string): number of deletions needed

Filling the DP Table

For each cell, we consider three possible operations:

1. Replace (or match): Look at diagonal (dp[i-1][j-1])
   • If characters match: copy diagonal value
   • If characters differ: diagonal value + 1
2. Delete: Look at cell above (dp[i-1][j]) + 1
3. Insert: Look at cell to left (dp[i][j-1]) + 1

Take minimum of these three values.

Let’s fill the first row after base cases:

    ''  r   o   s
''  0   1   2   3
h   1   1   2   3   <- Min operations to transform "h" to "r", "ro", "ros"
o   2   2   1   2
r   3   2   2   2
s   4   3   3   2
e   5   4   4   3   <- Final answer

Understanding Cell Values

Let’s break down how we got some key values:

1. dp[1][1] (h→r):

   • Replace ‘h’ with ‘r’: dp[0][0] + 1 = 1
   • Delete ‘h’: dp[0][1] + 1 = 2
   • Insert ‘r’: dp[1][0] + 1 = 2
   • Minimum = 1 (replace operation)

2. dp[2][2] (ho→ro):

   • Previous diagonal + 0 (characters match): dp[1][1] + 0 = 1
   • Delete: dp[1][2] + 1 = 4
   • Insert: dp[2][1] + 1 = 3
   • Minimum = 1 (match operation)

Solution Implementation

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        # Create DP table with base cases
        dp = [[0] * (n+1) for _ in range(m+1)]
        
        # Base cases: transforming to/from empty string
        for r in range(m+1):
            dp[r][0] = r    # Deletions needed
        for c in range(n+1):
            dp[0][c] = c    # Insertions needed
            
        # Fill DP table
        for r in range(1, m+1):
            for c in range(1, n+1):
                if word1[r-1] == word2[c-1]:
                    # Characters match - copy diagonal
                    dp[r][c] = dp[r-1][c-1]
                else:
                    # Take minimum of three operations
                    dp[r][c] = 1 + min(
                        dp[r][c-1],      # Insert
                        dp[r-1][c],      # Delete
                        dp[r-1][c-1]     # Replace
                    )
        
        return dp[m][n]

Complexity Analysis

• Time Complexity: $O(mn)$ where m and n are lengths of input strings
  • We need to fill every cell in the dp table once
• Space Complexity: $O(mn)$
  • We need to store the entire dp table