LeetEye LeetEye
Medium 2D Dynamic Programming ~5 min

Edit Distance

2d-dp edit-distance

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

Examples

Example 1
Input: word1 = "horse", word2 = "ros"
Output: 3
horse → rorse (replace 'h' with 'r')
Example 2
Input: word1 = "intention", word2 = "execution"
Output: 5
Key Insight

If characters match, no operation needed. Otherwise, try all three operations and take minimum.

Match → dp[i-1][j-1]. No match → 1 + min(insert dp[i][j-1], delete dp[i-1][j], replace dp[i-1][j-1]).

How to Approach This Problem

Pattern Recognition: When you see keywords like edit distance 2d-dp, think 2D Dynamic Programming.

Step-by-Step Reasoning

1 If word1[i-1] == word2[j-1]:
Answer: dp[i][j] = dp[i-1][j-1]
Characters match, no operation needed. Same as previous state.
2 Inserting into word1 corresponds to:
Answer: dp[i][j-1] + 1
Insert char to match word2[j-1]. Now need to match word1[0:i] with word2[0:j-1].
3 Deleting from word1 corresponds to:
Answer: dp[i-1][j] + 1
Delete word1[i-1]. Now need to match word1[0:i-1] with word2[0:j].
4 Replacing in word1 corresponds to:
Answer: dp[i-1][j-1] + 1
Replace word1[i-1] with word2[j-1]. Both chars now "match" (handled). Move diagonally.
5 dp[i][0] and dp[0][j] are:
Answer: dp[i][0] = i, dp[0][j] = j
Transform word1[0:i] to empty = i deletions. Transform empty to word2[0:j] = j insertions.

Solution

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    
    # Space-optimized: only need previous row
    prev = list(range(n + 1))  # Base: dp[0][j] = j
    
    for i in range(1, m + 1):
        curr = [i] + [0] * n  # Base: dp[i][0] = i
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                curr[j] = prev[j - 1]
            else:
                curr[j] = 1 + min(
                    curr[j - 1],   # Insert
                    prev[j],       # Delete
                    prev[j - 1]    # Replace
                )
        prev = curr
    
    return prev[n]

Complexity Analysis

Time O(m × n)
Space O(n)

Master This Pattern

Build intuition with interactive MCQs. Practice 2D Dynamic Programming problems in the LeetEye app.

Download LeetEye Free
Practice in LeetEye