Problem Description

This is the classic Edit Distance problem, also known as the Levenshtein Distance problem.

You are given two strings word1 and word2. Your task is to find the minimum number of operations needed to transform word1 into word2.

You can perform three types of operations on word1:

• Insert a character at any position
• Delete a character from any position
• Replace a character with another character

The problem uses dynamic programming to find the optimal solution. We create a 2D table f[i][j] where each cell represents the minimum operations needed to convert the first i characters of word1 to the first j characters of word2.

The base cases are:

• f[0][j] = j: Converting an empty string to the first j characters of word2 requires j insertions
• f[i][0] = i: Converting the first i characters of word1 to an empty string requires i deletions

For each cell f[i][j], we check if the current characters match:

• If word1[i-1] == word2[j-1], no operation is needed for these characters, so f[i][j] = f[i-1][j-1]
• Otherwise, we take the minimum of three possible operations and add 1:
  • f[i-1][j] + 1: Delete from word1
  • f[i][j-1] + 1: Insert into word1
  • f[i-1][j-1] + 1: Replace in word1

The final answer is stored in f[m][n], where m and n are the lengths of word1 and word2 respectively.

Intuition

The key insight is to think about this problem recursively and then optimize it using dynamic programming.

Imagine you're comparing two strings character by character from left to right. At each position, you face a decision: what's the best way to handle the current characters?

Let's say we're looking at position i in word1 and position j in word2. If the characters match (word1[i] == word2[j]), that's great! We don't need to do anything for these characters, and we can focus on the remaining parts of both strings.

But what if they don't match? We have three choices:

1. Delete the character from word1 - this means we skip this character in word1 and try to match the rest of word1 with word2
2. Insert a character into word1 - we add the matching character from word2, which moves us forward in word2 but stays at the same position in word1
3. Replace the character in word1 - we change it to match word2[j], allowing us to move forward in both strings

The brilliant part is recognizing that we can build up the solution incrementally. Instead of solving the entire problem at once, we solve smaller subproblems first. For example, what's the edit distance between empty strings? Between one character and empty string? Between two single characters?

This leads us to dynamic programming: we create a table where each cell f[i][j] represents a subproblem - converting the first i characters of word1 to the first j characters of word2. We fill this table systematically, using previously computed values to calculate new ones.

The recurrence relation captures our decision-making process:

• If characters match: f[i][j] = f[i-1][j-1] (no operation needed)
• If they don't match: f[i][j] = 1 + min(f[i-1][j], f[i][j-1], f[i-1][j-1]) (choose the cheapest operation)

By building up from smaller subproblems to larger ones, we avoid redundant calculations and efficiently find the minimum edit distance.

Learn more about Dynamic Programming patterns.

Solution Approach

We implement the solution using a 2D dynamic programming table f where f[i][j] represents the minimum number of operations to convert the first i characters of word1 to the first j characters of word2.

Step 1: Initialize the DP table

Create a (m+1) × (n+1) table where m = len(word1) and n = len(word2). The extra row and column handle the base cases of empty strings.

f = [[0] * (n + 1) for _ in range(m + 1)]

Step 2: Set up base cases

• First row f[0][j] = j: Converting empty string to first j characters of word2 requires j insertions
• First column f[i][0] = i: Converting first i characters of word1 to empty string requires i deletions

for j in range(1, n + 1):
    f[0][j] = j

Step 3: Fill the DP table

For each cell f[i][j], we apply the state transition equation:

The implementation uses enumerate(word1, 1) to iterate through characters while maintaining 1-based indexing for the DP table:

for i, a in enumerate(word1, 1):
    f[i][0] = i  # Set first column value
    for j, b in enumerate(word2, 1):
        if a == b:
            f[i][j] = f[i - 1][j - 1]  # Characters match, no operation needed
        else:
            # Take minimum of three operations:
            # f[i-1][j]: delete from word1
            # f[i][j-1]: insert into word1
            # f[i-1][j-1]: replace in word1
            f[i][j] = min(f[i - 1][j], f[i][j - 1], f[i - 1][j - 1]) + 1

Step 4: Return the result

The answer is in f[m][n], representing the minimum operations to convert entire word1 to entire word2.

Time Complexity: O(m × n) where m and n are the lengths of the two strings, as we fill each cell in the DP table once.

Space Complexity: O(m × n) for storing the DP table.

Example Walkthrough

Let's walk through converting word1 = "cat" to word2 = "cut" step by step.

Step 1: Initialize the DP table

We create a 4×4 table (since both strings have length 3, we need an extra row and column for empty string cases):

    ""  c  u  t
""  0   1  2  3
c   1   ?  ?  ?
a   2   ?  ?  ?
t   3   ?  ?  ?

The first row represents converting an empty string to "c", "cu", "cut" (requires 1, 2, 3 insertions respectively). The first column represents converting "c", "ca", "cat" to an empty string (requires 1, 2, 3 deletions respectively).

Step 2: Fill the table row by row

Row 1 (i=1, character 'c' from word1):

• f[1][1]: Compare 'c' with 'c' → They match! So f[1][1] = f[0][0] = 0
• f[1][2]: Compare 'c' with 'u' → They don't match. Take min of:
  • Delete 'c': f[0][2] + 1 = 2 + 1 = 3
  • Insert 'u': f[1][1] + 1 = 0 + 1 = 1
  • Replace 'c' with 'u': f[0][1] + 1 = 1 + 1 = 2
  • Minimum is 1, so f[1][2] = 1
• f[1][3]: Compare 'c' with 't' → They don't match. Take min of:
  • Delete 'c': f[0][3] + 1 = 3 + 1 = 4
  • Insert 't': f[1][2] + 1 = 1 + 1 = 2
  • Replace 'c' with 't': f[0][2] + 1 = 2 + 1 = 3
  • Minimum is 2, so f[1][3] = 2

    ""  c  u  t
""  0   1  2  3
c   1   0  1  2
a   2   ?  ?  ?
t   3   ?  ?  ?

Row 2 (i=2, character 'a' from word1):

• f[2][1]: Compare 'a' with 'c' → They don't match. Min(1+1, 0+1, 0+1) = 1
• f[2][2]: Compare 'a' with 'u' → They don't match. Min(0+1, 1+1, 0+1) = 1
• f[2][3]: Compare 'a' with 't' → They don't match. Min(1+1, 1+1, 1+1) = 2

    ""  c  u  t
""  0   1  2  3
c   1   0  1  2
a   2   1  1  2
t   3   ?  ?  ?

Row 3 (i=3, character 't' from word1):

• f[3][1]: Compare 't' with 'c' → They don't match. Min(2+1, 1+1, 1+1) = 2
• f[3][2]: Compare 't' with 'u' → They don't match. Min(1+1, 2+1, 1+1) = 2
• f[3][3]: Compare 't' with 't' → They match! So f[3][3] = f[2][2] = 1

Final table:

    ""  c  u  t
""  0   1  2  3
c   1   0  1  2
a   2   1  1  2
t   3   2  2  1

Result: f[3][3] = 1, meaning we need exactly 1 operation to convert "cat" to "cut".

The optimal operation is to replace 'a' with 'u', transforming "cat" → "cut" in one step.

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the length of word1 and n is the length of word2. This is because the algorithm uses a nested loop structure - the outer loop iterates through all characters of word1 (m iterations), and for each character, the inner loop iterates through all characters of word2 (n iterations). Each cell in the dynamic programming table is computed exactly once with constant time operations.

The space complexity is O(m × n). The algorithm creates a 2D array f with dimensions (m + 1) × (n + 1) to store the intermediate results for the dynamic programming solution. This table stores the minimum edit distance for all possible substrings of word1 and word2, requiring space proportional to the product of their lengths.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Index Confusion Between String and DP Table

One of the most common mistakes is confusing the indices when accessing characters from the strings versus the DP table. The DP table uses 1-based indexing (where dp[i][j] represents the first i characters of word1 and first j characters of word2), while string access uses 0-based indexing.

Incorrect Implementation:

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if word1[i] == word2[j]:  # Wrong! This causes IndexError
            dp[i][j] = dp[i-1][j-1]

Correct Implementation:

for i in range(1, m + 1):
    for j in range(1, n + 1):
        if word1[i-1] == word2[j-1]:  # Correct: use i-1 and j-1 for string access
            dp[i][j] = dp[i-1][j-1]

2. Forgetting to Initialize Base Cases Properly

Another pitfall is incomplete initialization of the DP table's first row and column. Some implementations forget to set the first column values inside the main loop or miss initializing them entirely.

Incorrect Implementation:

dp = [[0] * (n + 1) for _ in range(m + 1)]
# Forgot to initialize first row and column!
for i in range(1, m + 1):
    for j in range(1, n + 1):
        # ... rest of the logic

Correct Implementation:

dp = [[0] * (n + 1) for _ in range(m + 1)]

# Initialize first row
for j in range(1, n + 1):
    dp[0][j] = j

# Initialize first column (can be done in main loop or separately)
for i in range(1, m + 1):
    dp[i][0] = i
    for j in range(1, n + 1):
        # ... rest of the logic

3. Space Optimization Attempt Gone Wrong

When trying to optimize space complexity from O(m×n) to O(min(m,n)) using a 1D or 2-row approach, it's easy to overwrite values that are still needed.

Problematic Space-Optimized Version:

def minDistance(self, word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [j for j in range(n + 1)]  # Single row
  
    for i in range(1, m + 1):
        dp[0] = i  # Wrong! This overwrites the value we need for dp[1]
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[j] = dp[j-1]  # Wrong! dp[j-1] was already updated
            else:
                dp[j] = min(dp[j], dp[j-1], dp[j-1]) + 1

Correct Space-Optimized Version:

def minDistance(self, word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    # Make word1 the shorter string for better space efficiency
    if m > n:
        word1, word2, m, n = word2, word1, n, m
  
    prev = list(range(n + 1))
  
    for i in range(1, m + 1):
        curr = [i] + [0] * n
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                curr[j] = prev[j-1]
            else:
                curr[j] = min(prev[j], curr[j-1], prev[j-1]) + 1
        prev = curr
  
    return prev[n]

4. Not Handling Edge Cases

Failing to consider empty strings or identical strings can lead to unnecessary computation or errors.

Better Implementation with Early Returns:

def minDistance(self, word1: str, word2: str) -> int:
    # Handle edge cases
    if word1 == word2:
        return 0
    if not word1:
        return len(word2)
    if not word2:
        return len(word1)
  
    # Continue with standard DP solution...