Edit Distance

HardDynamic ProgrammingString2D DP
Category: 2-D Dynamic Programming
Companies that ask this question:
AmazonGoogleFacebookMicrosoftBloomberg

Approach

Edit Distance

Problem Statement

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
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.

Approach

Key Insight

Classic 2D Dynamic Programming problem!

Define dp[i][j] = minimum edit distance to convert word1[0..i-1] to word2[0..j-1]

Solution 1: 2D Dynamic Programming

Build a 2D table where each cell represents the minimum operations needed.

Algorithm:

  1. Create dp[m+1][n+1] table
  2. Base cases:
    • dp[0][j] = j (insert j characters)
    • dp[i][0] = i (delete i characters)
  3. For each cell dp[i][j]:
    • If word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] (no operation)
    • Else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
      • dp[i-1][j] + 1: delete from word1
      • dp[i][j-1] + 1: insert to word1
      • dp[i-1][j-1] + 1: replace in word1
  4. Return dp[m][n]

Complexity:

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

Solution 2: Space Optimized (1D Array)

Use only two rows instead of full 2D table.

Algorithm:

  1. Use two 1D arrays: prev and curr
  2. Alternate between them for each row
  3. Same recurrence relation
  4. Return curr[n]

Complexity:

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

Solution 3: Recursion with Memoization

Top-down approach with memoization.

Algorithm:

  1. Define recursive function: editDistance(i, j)
  2. Base cases: i=0 return j, j=0 return i
  3. If chars match: recurse without operation
  4. Else: try all three operations, take minimum
  5. Memoize results

Complexity:

  • Time: O(m × n) with memoization
  • Space: O(m × n) for memo + O(m+n) recursion stack

Complexity Analysis

| Approach | Time | Space | |----------|------|-------| | 2D DP | O(m × n) | O(m × n) | | Space Optimized | O(m × n) | O(n) | | Memoization | O(m × n) | O(m × n) |

Pattern Recognition

This problem demonstrates:

  • 2D Dynamic Programming classic pattern
  • Levenshtein Distance algorithm
  • Three-way min decision at each step
  • Similar patterns: Longest Common Subsequence, Distinct Subsequences
  • Applications: Spell check, DNA sequence alignment, diff tools

Solution

java
1import java.util.*;
2
3class Solution {
4    // Solution 1: 2D Dynamic Programming
5    public int minDistance(String word1, String word2) {
6        int m = word1.length();
7        int n = word2.length();
8
9        // dp[i][j] = min operations to convert word1[0..i-1] to word2[0..j-1]
10        int[][] dp = new int[m + 1][n + 1];
11
12        // Base cases
13        for (int i = 0; i <= m; i++) {
14            dp[i][0] = i;  // Delete all characters from word1
15        }
16
17        for (int j = 0; j <= n; j++) {
18            dp[0][j] = j;  // Insert all characters to match word2
19        }
20
21        // Fill the DP table
22        for (int i = 1; i <= m; i++) {
23            for (int j = 1; j <= n; j++) {
24                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
25                    // Characters match, no operation needed
26                    dp[i][j] = dp[i - 1][j - 1];
27                } else {
28                    // Take minimum of three operations
29                    dp[i][j] = 1 + Math.min(
30                        dp[i - 1][j],      // Delete from word1
31                        Math.min(
32                            dp[i][j - 1],      // Insert to word1
33                            dp[i - 1][j - 1]   // Replace in word1
34                        )
35                    );
36                }
37            }
38        }
39
40        return dp[m][n];
41    }
42
43    // Solution 2: Space Optimized (Two Arrays)
44    public int minDistanceOptimized(String word1, String word2) {
45        int m = word1.length();
46        int n = word2.length();
47
48        // Use two arrays instead of 2D table
49        int[] prev = new int[n + 1];
50        int[] curr = new int[n + 1];
51
52        // Initialize base case
53        for (int j = 0; j <= n; j++) {
54            prev[j] = j;
55        }
56
57        for (int i = 1; i <= m; i++) {
58            curr[0] = i;  // Base case for current row
59
60            for (int j = 1; j <= n; j++) {
61                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
62                    curr[j] = prev[j - 1];
63                } else {
64                    curr[j] = 1 + Math.min(
65                        prev[j],      // Delete
66                        Math.min(
67                            curr[j - 1],  // Insert
68                            prev[j - 1]   // Replace
69                        )
70                    );
71                }
72            }
73
74            // Swap arrays
75            int[] temp = prev;
76            prev = curr;
77            curr = temp;
78        }
79
80        return prev[n];
81    }
82
83    // Solution 3: Recursion with Memoization
84    public int minDistanceMemo(String word1, String word2) {
85        Map<String, Integer> memo = new HashMap<>();
86        return dp(word1, word2, word1.length(), word2.length(), memo);
87    }
88
89    private int dp(String word1, String word2, int i, int j, Map<String, Integer> memo) {
90        // Base cases
91        if (i == 0) return j;  // Insert j characters
92        if (j == 0) return i;  // Delete i characters
93
94        // Check memo
95        String key = i + "," + j;
96        if (memo.containsKey(key)) {
97            return memo.get(key);
98        }
99
100        int result;
101        if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
102            // Characters match
103            result = dp(word1, word2, i - 1, j - 1, memo);
104        } else {
105            // Try all three operations
106            result = 1 + Math.min(
107                dp(word1, word2, i - 1, j, memo),      // Delete
108                Math.min(
109                    dp(word1, word2, i, j - 1, memo),      // Insert
110                    dp(word1, word2, i - 1, j - 1, memo)   // Replace
111                )
112            );
113        }
114
115        memo.put(key, result);
116        return result;
117    }
118
119    // Solution 4: With Path Reconstruction
120    public static class Result {
121        public int distance;
122        public List<String> operations;
123
124        public Result(int distance, List<String> operations) {
125            this.distance = distance;
126            this.operations = operations;
127        }
128    }
129
130    public Result minDistanceWithPath(String word1, String word2) {
131        int m = word1.length();
132        int n = word2.length();
133        int[][] dp = new int[m + 1][n + 1];
134
135        // Base cases
136        for (int i = 0; i <= m; i++) {
137            dp[i][0] = i;
138        }
139        for (int j = 0; j <= n; j++) {
140            dp[0][j] = j;
141        }
142
143        // Fill DP table
144        for (int i = 1; i <= m; i++) {
145            for (int j = 1; j <= n; j++) {
146                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
147                    dp[i][j] = dp[i - 1][j - 1];
148                } else {
149                    dp[i][j] = 1 + Math.min(
150                        dp[i - 1][j],
151                        Math.min(dp[i][j - 1], dp[i - 1][j - 1])
152                    );
153                }
154            }
155        }
156
157        // Reconstruct path
158        List<String> operations = new ArrayList<>();
159        int i = m, j = n;
160
161        while (i > 0 || j > 0) {
162            if (i == 0) {
163                operations.add("Insert '" + word2.charAt(j - 1) + "'");
164                j--;
165            } else if (j == 0) {
166                operations.add("Delete '" + word1.charAt(i - 1) + "'");
167                i--;
168            } else if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
169                i--;
170                j--;
171            } else {
172                // Find which operation was used
173                int deleteCost = dp[i - 1][j];
174                int insertCost = dp[i][j - 1];
175                int replaceCost = dp[i - 1][j - 1];
176
177                int minCost = Math.min(deleteCost, Math.min(insertCost, replaceCost));
178
179                if (minCost == replaceCost) {
180                    operations.add(
181                        "Replace '" + word1.charAt(i - 1) + "' with '" + word2.charAt(j - 1) + "'"
182                    );
183                    i--;
184                    j--;
185                } else if (minCost == deleteCost) {
186                    operations.add("Delete '" + word1.charAt(i - 1) + "'");
187                    i--;
188                } else {
189                    operations.add("Insert '" + word2.charAt(j - 1) + "'");
190                    j--;
191                }
192            }
193        }
194
195        Collections.reverse(operations);
196        return new Result(dp[m][n], operations);
197    }
198}
199
Loading visualizer...