Edit Distance

LeetCode 72: Edit Distance Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes a 2D Dynamic Programming table where each cell (i, j) stores the minimum operations required to convert the first i characters of word1 to the first j characters of word2.

The Edit Distance problem asks us to determine the minimum number of operations required to transform one string (word1) into another (word2). We are allowed three specific operations: inserting a character, deleting a character, or replacing a character. This metric is also widely known as the Levenshtein Distance. This is a popular interview question frequently asked by top tech companies like Google and Amazon to test proficiency in string manipulation and optimization.

Brute Force Approach for Edit Distance

The naive approach to solving the LeetCode 72 Edit Distance problem involves recursion. We can define a function calculate(i, j) that computes the edit distance between word1[0...i] and word2[0...j].

For every pair of characters at indices i and j:

1. If the characters match (word1[i] == word2[j]), no operation is needed for this position. We recurse on the remaining substrings: calculate(i-1, j-1).
2. If they do not match, we must perform one of the three operations. We try all three recursively and take the minimum:
   • Insert: 1 + calculate(i, j-1)
   • Delete: 1 + calculate(i-1, j)
   • Replace: 1 + calculate(i-1, j-1)

Pseudo-code

function solve(i, j):
    if i < 0: return j + 1  // word1 is empty, insert remaining word2
    if j < 0: return i + 1  // word2 is empty, delete remaining word1
    
    if word1[i] == word2[j]:
        return solve(i - 1, j - 1)
    else:
        return 1 + min(
            solve(i, j - 1),    // Insert
            solve(i - 1, j),    // Delete
            solve(i - 1, j - 1) // Replace
        )

Time Complexity Analysis

The time complexity of this brute force approach is exponential, specifically $O(3^{\max(m, n)})$, where $m$ and $n$ are the lengths of the strings. This occurs because every mismatch branches into three subproblems.

Why it Fails

This approach fails due to Time Limit Exceeded (TLE) on LeetCode. The recursion tree contains massive overlapping subproblems. For example, computing the state for indices (i-1, j-1) is required by the "Replace" branch of (i, j), the "Delete" branch of (i, j-1), and the "Insert" branch of (i-1, j). Without caching these results, the algorithm performs redundant calculations for the same states millions of times.

Algorithm Strategy: DP - 2D Array

We construct a 2D integer array dp of size (m + 1) x (n + 1). dp[i][j] will store the minimum edit distance between the first i characters of word1 and the first j characters of word2.

1. Initialization (Base Cases)

• The 0-th row represents transforming an empty word1 into word2 prefixes. This requires j insertions. So, dp[0][j] = j.
• The 0-th column represents transforming word1 prefixes into an empty word2. This requires i deletions. So, dp[i][0] = i.

2. State Transition

We iterate through the grid from i = 1 to m and j = 1 to n.

• If word1[i-1] == word2[j-1]: The current characters match. No new operation is needed. dp[i][j] = dp[i-1][j-1]
• If word1[i-1] != word2[j-1]: We take the minimum of the three possible previous states plus 1 (for the current operation). dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
  • dp[i-1][j] represents Deletion.
  • dp[i][j-1] represents Insertion.
  • dp[i-1][j-1] represents Replacement.

3. Final Answer

The value at dp[m][n] contains the minimum operations to convert the entire word1 to word2.

Execution Flow

Let's trace word1 = "horse", word2 = "ros".

1. Initialize Table: Create a 6x4 table.

   • Row 0 becomes [0, 1, 2, 3] (insertions to form "", "r", "ro", "ros").
   • Col 0 becomes [0, 1, 2, 3, 4, 5] (deletions from "h", "ho", "hor", ...).

2. Fill Row 1 ('h' vs "ros"):

   • 'h' vs 'r': Mismatch. Min of neighbors (0, 1, 1) + 1. dp[1][1] = 1 (Replace 'h'->'r').
   • 'h' vs 'o': Mismatch. Neighbor dp[1][1] is 1. dp[1][2] = 2 (Replace+Insert).
   • 'h' vs 's': Mismatch. dp[1][3] = 3.

3. Fill Row 2 ('o' vs "ros"):

   • 'o' vs 'r': Mismatch. dp[2][1] = 2.
   • 'o' vs 'o': Match. Inherit diagonal dp[1][1]. dp[2][2] = 1 (Replace 'h'->'r', keep 'o').
   • 'o' vs 's': Mismatch. dp[2][3] = 2.

4. Fill Row 3 ('r' vs "ros"):

   • 'r' vs 'r': Match. Inherit diagonal dp[2][0]. dp[3][1] = 2.
   • ... process continues ...

5. Final Cell:

   • The value at dp[5][3] will be 3.

Proof of Correctness

The correctness follows from induction.

• Base Case: The initialization correctly handles empty strings (transforming length k to 0 requires k deletions; 0 to k requires k insertions).
• Inductive Step: Assume dp[x][y] is correct for all x <= i, y <= j (excluding dp[i][j]). The value dp[i][j] is computed by taking the minimum cost of reaching any valid previous state (i-1, j, i, j-1, or i-1, j-1) and adding the cost of the transition. Since these three previous states cover all possible last operations (delete, insert, replace/match), and we greedily choose the minimum, dp[i][j] must be optimal.

Pattern Reuse Notes

The 2D Dynamic Programming pattern used in LeetCode 72 is highly versatile.

• LeetCode 583: Delete Operation for Two Strings: This is a variation where "Replace" is not allowed, or equivalently, the cost of replacement is infinity (or 2 operations: delete + insert). The structure of the DP table remains identical.
• LeetCode 712: Minimum ASCII Delete Sum for Two Strings: Instead of counting the number of operations, you sum the ASCII values of deleted characters. The logic is the same, but the cost function changes from +1 to +ascii_value.

Reference Implementation

C++ Solution for LeetCode 72

1class Solution {
2public:
3    int minDistance(string word1, string word2) {
4        int m = word1.length();
5        int n = word2.length();
6        
7        // dp[i][j] represents the min operations to convert word1[0..i-1] to word2[0..j-1]
8        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
9
10        // Base cases: transforming empty string to/from non-empty string
11        for (int i = 0; i <= m; i++) {
12            dp[i][0] = i;
13        }
14        for (int j = 0; j <= n; j++) {
15            dp[0][j] = j;
16        }
17
18        // Fill DP table
19        for (int i = 1; i <= m; i++) {
20            for (int j = 1; j <= n; j++) {
21                if (word1[i - 1] == word2[j - 1]) {
22                    // Characters match, no new operation needed
23                    dp[i][j] = dp[i - 1][j - 1];
24                } else {
25                    // Mismatch: take minimum of insert, delete, replace + 1
26                    dp[i][j] = 1 + min({
27                        dp[i - 1][j],    // Delete
28                        dp[i][j - 1],    // Insert
29                        dp[i - 1][j - 1] // Replace
30                    });
31                }
32            }
33        }
34
35        return dp[m][n];
36    }
37};

Java Solution for LeetCode 72

1class Solution {
2    public int minDistance(String word1, String word2) {
3        int m = word1.length();
4        int n = word2.length();
5        
6        // dp[i][j] will be the edit distance between word1[0..i-1] and word2[0..j-1]
7        int[][] dp = new int[m + 1][n + 1];
8
9        // Initialize base cases
10        for (int i = 0; i <= m; i++) {
11            dp[i][0] = i; // Deleting all characters from word1
12        }
13        for (int j = 0; j <= n; j++) {
14            dp[0][j] = j; // Inserting all characters to match word2
15        }
16
17        // Compute DP table
18        for (int i = 1; i <= m; i++) {
19            for (int j = 1; j <= n; j++) {
20                // Note: String charAt is 0-indexed, so we check i-1 and j-1
21                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
22                    dp[i][j] = dp[i - 1][j - 1];
23                } else {
24                    int insert = dp[i][j - 1];
25                    int delete = dp[i - 1][j];
26                    int replace = dp[i - 1][j - 1];
27                    
28                    dp[i][j] = 1 + Math.min(replace, Math.min(insert, delete));
29                }
30            }
31        }
32
33        return dp[m][n];
34    }
35}

Python Solution for LeetCode 72

1class Solution:
2    def minDistance(self, word1: str, word2: str) -> int:
3        m, n = len(word1), len(word2)
4        
5        # dp[i][j] stores the edit distance between word1[:i] and word2[:j]
6        dp = [[0] * (n + 1) for _ in range(m + 1)]
7        
8        # Base cases
9        for i in range(m + 1):
10            dp[i][0] = i
11        for j in range(n + 1):
12            dp[0][j] = j
13            
14        # Iterate through the grid
15        for i in range(1, m + 1):
16            for j in range(1, n + 1):
17                if word1[i - 1] == word2[j - 1]:
18                    # If characters match, inherit from diagonal
19                    dp[i][j] = dp[i - 1][j - 1]
20                else:
21                    # If mismatch, take min of insert, delete, replace + 1
22                    dp[i][j] = 1 + min(
23                        dp[i - 1][j],    # Delete
24                        dp[i][j - 1],    # Insert
25                        dp[i - 1][j - 1] # Replace
26                    )
27                    
28        return dp[m][n]