Edit Distance
Problem
Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2, where operations are insert, delete, or replace a character.
- 0 ≤ word1.length, word2.length ≤ 500
- word1 and word2 consist of lowercase English letters.
Example
word1 = "horse", word2 = "ros"3Transform "horse" to "ros" with minimum operations: 1. Replace 'h' with 'r' → "rorse" 2. Delete 'r' → "rose" 3. Delete 'e' → "ros" The algorithm recursively compares characters from the end of both strings, exploring insert, delete, and replace operations when characters differ, and memoizes results to avoid redundant computations.
Approach
Straightforward Solution
A brute-force recursive approach tries all possible operations at each mismatch, leading to exponential time complexity due to repeated subproblems.
Core Observation
The minimum edit distance between prefixes of the two strings depends on the minimum edit distances of smaller prefixes, revealing overlapping subproblems and optimal substructure.
Path to Optimal
Recognizing the problem's overlapping subproblems and optimal substructure suggests dynamic programming. By defining a recursive function dp(i, j) representing the minimum edit distance between word1[:i+1] and word2[:j+1], and memoizing results, redundant computations are eliminated. The recursion handles base cases when one string is empty, and for each character mismatch, it considers insert, delete, and replace operations, choosing the minimal cost.
Optimal Approach
Use a top-down recursive DP with memoization. The dp(i, j) function returns the minimum operations to convert word1[0..i] to word2[0..j]. If characters match, recurse on dp(i-1, j-1). Otherwise, compute the minimum among insert (dp(i, j-1)), delete (dp(i-1, j)), and replace (dp(i-1, j-1)) plus one operation. Memoize results to achieve O(m*n) time complexity, where m and n are the lengths of the input strings.
Time
O(m * n)
Each state (i, j) representing prefixes of word1 and word2 is computed once and stored in memo. There are m * n such states, and each computation does O(1) work.
Space
O(m * n)
The memoization dictionary stores results for all pairs of indices (i, j), requiring O(m * n) auxiliary space. The recursion stack depth is at most O(m + n), which is dominated by the memo size.
Pattern Spotlight
Dynamic Programming (Top-Down Memoization for Sequence Alignment)
When a problem asks for minimum operations to transform one sequence into another with insert/delete/replace, model it as a state machine over indices and use memoized recursion to avoid recomputation of overlapping subproblems.
Solution
| 1 | class Solution:
|
| 2 | def minDistance(self, word1: str, word2: str) -> int:
|
| 3 | memo = {}
|
| 4 |
|
| 5 | def dp(i, j):
|
| 6 | if i < 0:
|
| 7 | return j + 1
|
| 8 | if j < 0:
|
| 9 | return i + 1
|
| 10 | if (i, j) in memo:
|
| 11 | return memo[(i, j)]
|
| 12 |
|
| 13 | if word1[i] == word2[j]:
|
| 14 | result = dp(i - 1, j - 1)
|
| 15 | else:
|
| 16 | insert = dp(i, j - 1)
|
| 17 | delete = dp(i - 1, j)
|
| 18 | replace = dp(i - 1, j - 1)
|
| 19 | result = 1 + min(insert, delete, replace)
|
| 20 |
|
| 21 | memo[(i, j)] = result
|
| 22 | return result
|
| 23 |
|
| 24 | return dp(len(word1) - 1, len(word2) - 1) |
| 1 | import java.util.HashMap; |
| 2 | import java.util.Map; |
| 3 | |
| 4 | public class Solution { |
| 5 | public int minDistance(String word1, String word2) { |
| 6 | Map<String, Integer> memo = new HashMap<>(); |
| 7 | |
| 8 | return dp(word1, word2, word1.length() - 1, word2.length() - 1, memo); |
| 9 | } |
| 10 | |
| 11 | private int dp(String word1, String word2, int i, int j, Map<String, Integer> memo) { |
| 12 | if (i < 0) { |
| 13 | return j + 1; |
| 14 | } |
| 15 | if (j < 0) { |
| 16 | return i + 1; |
| 17 | } |
| 18 | String key = i + "," + j; |
| 19 | if (memo.containsKey(key)) { |
| 20 | return memo.get(key); |
| 21 | } |
| 22 | |
| 23 | int result; |
| 24 | if (word1.charAt(i) == word2.charAt(j)) { |
| 25 | result = dp(word1, word2, i - 1, j - 1, memo); |
| 26 | } else { |
| 27 | int insert = dp(word1, word2, i, j - 1, memo); |
| 28 | int delete = dp(word1, word2, i - 1, j, memo); |
| 29 | int replace = dp(word1, word2, i - 1, j - 1, memo); |
| 30 | result = 1 + Math.min(insert, Math.min(delete, replace)); |
| 31 | } |
| 32 | |
| 33 | memo.put(key, result); |
| 34 | return result; |
| 35 | } |
| 36 | } |
| 1 | #include <string> |
| 2 | #include <unordered_map> |
| 3 | #include <utility> |
| 4 | #include <algorithm> |
| 5 | |
| 6 | using namespace std; |
| 7 | |
| 8 | class Solution { |
| 9 | public: |
| 10 | int minDistance(string word1, string word2) { |
| 11 | return dp(word1, word2, (int)word1.size() - 1, (int)word2.size() - 1); |
| 12 | } |
| 13 | |
| 14 | private: |
| 15 | unordered_map<long long, int> memo; |
| 16 | |
| 17 | int dp(const string& word1, const string& word2, int i, int j) { |
| 18 | if (i < 0) return j + 1; |
| 19 | if (j < 0) return i + 1; |
| 20 | |
| 21 | long long key = ((long long)i << 32) | (unsigned int)j; |
| 22 | auto it = memo.find(key); |
| 23 | if (it != memo.end()) return it->second; |
| 24 | |
| 25 | int result; |
| 26 | if (word1[i] == word2[j]) { |
| 27 | result = dp(word1, word2, i - 1, j - 1); |
| 28 | } else { |
| 29 | int insert_op = dp(word1, word2, i, j - 1); |
| 30 | int delete_op = dp(word1, word2, i - 1, j); |
| 31 | int replace_op = dp(word1, word2, i - 1, j - 1); |
| 32 | result = 1 + min({insert_op, delete_op, replace_op}); |
| 33 | } |
| 34 | |
| 35 | memo[key] = result; |
| 36 | return result; |
| 37 | } |
| 38 | }; |
| 1 | var minDistance = function(word1, word2) { |
| 2 | const memo = new Map(); |
| 3 | |
| 4 | function dp(i, j) { |
| 5 | if (i < 0) return j + 1; |
| 6 | if (j < 0) return i + 1; |
| 7 | |
| 8 | const key = i + ',' + j; |
| 9 | if (memo.has(key)) return memo.get(key); |
| 10 | |
| 11 | let result; |
| 12 | if (word1[i] === word2[j]) { |
| 13 | result = dp(i - 1, j - 1); |
| 14 | } else { |
| 15 | const insert = dp(i, j - 1); |
| 16 | const del = dp(i - 1, j); |
| 17 | const replace = dp(i - 1, j - 1); |
| 18 | result = 1 + Math.min(insert, del, replace); |
| 19 | } |
| 20 | |
| 21 | memo.set(key, result); |
| 22 | return result; |
| 23 | } |
| 24 | |
| 25 | return dp(word1.length - 1, word2.length - 1); |
| 26 | }; |
Step-by-Step Solution
Implement Base Cases for Empty Prefixes
| 6 | if i < 0:
|
| 7 | return j + 1
|
| 8 | if j < 0:
|
| 9 | return i + 1
|
Objective
To handle the scenarios where one string prefix is empty, requiring insertions or deletions equal to the length of the other prefix.
Key Insight
When one index is less than zero, it means one string is fully consumed. The minimum operations to convert an empty string to a prefix of length j is j insertions (or deletions if the other string is empty). This base case anchors the recursion and prevents invalid index access.
Interview Quick-Check
Core Logic
Base cases return the length of the remaining prefix of the other string, representing the minimal insert/delete operations needed.
State & Boundaries
Check for i < 0 or j < 0 to handle empty prefix conditions correctly.
Use Memoization to Avoid Redundant Computations
| 3 | memo = {}
|
| 10 | if (i, j) in memo:
|
| 11 | return memo[(i, j)]
|
| 21 | memo[(i, j)] = result
|
Objective
To cache and reuse results of subproblems identified by indices (i, j) to prevent exponential recursion.
Key Insight
The recursive calls overlap heavily, as many subproblems are revisited multiple times. Storing computed results in a memo dictionary keyed by (i, j) ensures each unique subproblem is solved once, transforming the recursion into efficient dynamic programming.
Interview Quick-Check
Core Logic
Memoization lookup returns cached results immediately, avoiding repeated work.
Common Pitfalls & Bugs
Forgetting to memoize results leads to exponential time complexity and timeouts.
Recursively Compute Edit Distance with Character Comparison
| 13 | if word1[i] == word2[j]:
|
| 14 | result = dp(i - 1, j - 1)
|
| 15 | else:
|
| 16 | insert = dp(i, j - 1)
|
| 17 | delete = dp(i - 1, j)
|
| 18 | replace = dp(i - 1, j - 1)
|
| 19 | result = 1 + min(insert, delete, replace)
|
| 22 | return result
|
| 24 | return dp(len(word1) - 1, len(word2) - 1) |
Objective
To recursively compute the minimum edit distance by comparing characters and exploring insert, delete, and replace operations when characters differ.
Key Insight
If characters at indices i and j match, no operation is needed, so recurse on dp(i-1, j-1). Otherwise, consider the cost of inserting, deleting, or replacing a character, and choose the minimal cost plus one operation. This captures all possible transformations and ensures the minimal edit distance is found.
Interview Quick-Check
Core Logic
The recursion explores all three operations at mismatches and picks the minimal cost, embodying the principle of optimal substructure.
Common Pitfalls & Bugs
Incorrectly handling the indices or forgetting to add one to the operation cost leads to wrong answers.
Line Analysis
This solution has 6 Critical lines interviewers watch for.
result = 1 + min(insert, delete, replace)Calculate minimal cost among insert, delete, and replace plus one operation.
This min operation is the heart of the DP recurrence; it tries all possible edit operations and picks the one with the least cost, guaranteeing the minimal edit distance.
if i < 0:Return the number of insertions needed when word1 prefix is empty.
If i < 0, word1 is empty, so converting to word2[:j+1] requires j+1 insertions, which is the minimal operation count.
if j < 0:Return the number of deletions needed when word2 prefix is empty.
If j < 0, word2 is empty, so converting word1[:i+1] to empty requires i+1 deletions, the minimal operation count.
if (i, j) in memo:Check if the current subproblem result is cached in memo.
This lookup prevents redundant recursive calls by returning previously computed results immediately, critical for efficiency.
else:Handle the case when characters differ by exploring all operations.
This conditional branch triggers exploration of all possible edit operations, which is the core of the edit distance calculation.
memo[(i, j)] = resultCache the computed result for the current subproblem.
Memoizing the result ensures that future calls with the same indices return instantly, preventing exponential recomputation.
memo = {}Initialize a memoization dictionary to cache subproblem results.
Memoization is essential to avoid exponential recomputation by storing results of dp(i, j) states, enabling efficient top-down dynamic programming.
return memo[(i, j)]Return the cached result for the current subproblem.
Returning memoized results prunes the recursion tree, collapsing exponential calls into polynomial time.
if word1[i] == word2[j]:Check if characters at current indices match.
Matching characters require no operation, allowing recursion to proceed without incrementing cost, which optimizes the solution.
result = dp(i - 1, j - 1)Recurse on previous indices when characters match.
This step leverages the optimal substructure by reducing the problem size without additional cost when characters are equal.
replace = dp(i - 1, j - 1)Compute cost of replacing a character.
Replacement corresponds to matching word1[:i] with word2[:j], then substituting one character, reflecting one operation.
return resultReturn the computed minimal edit distance for the current subproblem.
Returning the memoized result completes the recursion step, propagating the minimal cost upward.
return dp(len(word1) - 1, len(word2) - 1)Initiate the recursive computation from the full strings' last indices.
Starting from the last characters of both strings sets the recursion to cover the entire problem space, ensuring the final answer is computed.
return j + 1Return the insertion count for empty word1 prefix.
This return finalizes the base case for empty word1 prefix, ensuring correct recursion termination.
return i + 1Return the deletion count for empty word2 prefix.
This return finalizes the base case for empty word2 prefix, ensuring correct recursion termination.
insert = dp(i, j - 1)Compute cost of inserting a character.
Insertion corresponds to matching word1[:i+1] with word2[:j], then adding one character to word2, reflecting one operation.
delete = dp(i - 1, j)Compute cost of deleting a character.
Deletion corresponds to matching word1[:i] with word2[:j+1], then removing one character from word1, reflecting one operation.
Test Your Understanding
Why does memoization reduce the time complexity from exponential to polynomial in this problem?
Because memoization ensures each subproblem defined by indices (i, j) is solved only once, preventing repeated recursive calls on the same states and collapsing an exponential recursion tree into a polynomial number of unique states.
Related Problems
Dynamic Programming pattern
Don't just read it. Drill it.
Reconstruct Edit Distance from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Edit Distance drill