245. Edit Distance
🔗 LeetCode Problem: 72. Edit Distance
📊 Difficulty: Hard
🏷️ Topics: Dynamic Programming, String, DP - Strings
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
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.
🧒 Let's Build Understanding from Absolute Scratch
What Does This Problem REALLY Ask?
Forget "edit distance" for a moment. Let me understand what we're doing:
Given: word1 = "cat", word2 = "dog"
Question: How many changes needed to transform word1 into word2?
Let me try:
word1 = "cat"
word2 = "dog"
Step 1: Replace 'c' with 'd' → "dat"
Step 2: Replace 'a' with 'o' → "dot"
Step 3: Replace 't' with 'g' → "dog" ✓
Total: 3 operations
Can I do better? Let me think...
No! Every character is different!
Minimum operations = 3 ✓
Another example: word1 = "cat", word2 = "cut"
Step 1: Replace 'a' with 'u' → "cut" ✓
Total: 1 operation
Much better! Only one character different!
KEY INSIGHT: We want the MINIMUM number of operations! 🔑
Understanding the Three Operations
OPERATION 1: INSERT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Add a character anywhere in word1
Examples:
"cat" → INSERT 's' at start → "scat"
"cat" → INSERT 's' at end → "cats"
"cat" → INSERT 's' in middle → "cast"
Use case:
word1 = "cat", word2 = "cats"
INSERT 's' at end → "cats" ✓
1 operation!
OPERATION 2: DELETE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Remove a character from word1
Examples:
"cats" → DELETE 's' → "cat"
"hello" → DELETE first 'l' → "helo"
Use case:
word1 = "cats", word2 = "cat"
DELETE 's' → "cat" ✓
1 operation!
OBSERVATION: DELETE from word1 is like INSERT into word2!
word1="cats" → "cat" (delete 's' from word1)
word2="cat" → "cats" (insert 's' into word2)
Same result, different perspective! 🤔
OPERATION 3: REPLACE
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Change one character to another
Examples:
"cat" → REPLACE 'c' with 'd' → "dat"
"hello" → REPLACE 'e' with 'a' → "hallo"
Use case:
word1 = "cat", word2 = "cut"
REPLACE 'a' with 'u' → "cut" ✓
1 operation!
OBSERVATION: REPLACE is powerful!
Changes one character in one operation!
Better than DELETE + INSERT (2 operations)!
Why Is This Problem Hard?
The challenge: We have CHOICES at each step!
Example: word1 = "cat", word2 = "cut"
At position 1 (different: 'a' vs 'u'):
Choice 1: REPLACE 'a' with 'u' → "cut" (1 operation) ✓
Choice 2: DELETE 'a', INSERT 'u' → "cut" (2 operations) ✗
Choice 3: DELETE 'c', INSERT 'c', REPLACE... (many operations) ✗
We need to choose the BEST option!
Another example: word1 = "horse", word2 = "ros"
Many possible transformation paths:
Path 1: horse → rorse → rose → ros (3 operations) ✓
Path 2: horse → orse → ose → os → ros (4 operations) ✗
Path 3: ... many other paths ...
Which path is optimal? 🤔
INSIGHT: This is an OPTIMIZATION problem!
Try different choices, find minimum!
This screams DYNAMIC PROGRAMMING! 🔑
🤔 Building Intuition - The Recursive Structure
Understanding Character-by-Character Comparison
Let me think about comparing two strings:
word1 = "cat"
word2 = "cut"
Compare character by character:
Position 0: 'c' == 'c' ✓
They match! No operation needed!
Continue to next position!
Position 1: 'a' != 'u' ✗
They don't match! Need an operation!
What are my choices?
1. REPLACE 'a' with 'u' → word1 becomes "cut"
Then solve: "t" vs "t" → 0 operations
Total: 1 operation ✓
2. DELETE 'a' → word1 becomes "ct"
Then solve: "ct" vs "cut" → need more operations
Total: 1 + more operations ✗
3. INSERT 'u' → word1 becomes "cuat"
Then solve: "cuat" vs "cut" → need more operations
Total: 1 + more operations ✗
Best choice: REPLACE! (1 operation total)
This suggests we should compare positions! 🎯
The Recursive Insight
Define: editDistance(i, j) = minimum operations to convert
word1[i..] to word2[j..]
What this means:
- word1[i..] is substring of word1 starting from index i
- word2[j..] is substring of word2 starting from index j
- Return minimum operations needed
Base cases:
BASE CASE 1: word1 exhausted (i == len(word1))
word1 is empty, word2 has characters remaining
Need to INSERT all remaining characters from word2
Operations = len(word2) - j
Example: word1="", word2="cat"
INSERT 'c', INSERT 'a', INSERT 't' → 3 operations
BASE CASE 2: word2 exhausted (j == len(word2))
word2 is empty, word1 has characters remaining
Need to DELETE all remaining characters from word1
Operations = len(word1) - i
Example: word1="cat", word2=""
DELETE 'c', DELETE 'a', DELETE 't' → 3 operations
Recursive cases:
CASE 1: Characters match (word1[i] == word2[j])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Characters are the same! No operation needed!
Just move to next position:
editDistance(i, j) = editDistance(i+1, j+1)
Example: word1="cat", word2="cot", i=0, j=0
'c' == 'c' → no operation
Continue with "at" vs "ot"
CASE 2: Characters don't match (word1[i] != word2[j])
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Need an operation! Three choices:
Choice A: REPLACE word1[i] with word2[j]
Cost: 1 operation
After: word1[i] becomes word2[j]
Remaining: both strings move forward
editDistance(i, j) = 1 + editDistance(i+1, j+1)
Choice B: DELETE word1[i]
Cost: 1 operation
After: word1[i] is removed
Remaining: word1 moves forward, word2 stays
editDistance(i, j) = 1 + editDistance(i+1, j)
Choice C: INSERT word2[j] into word1
Cost: 1 operation
After: word1 has word2[j] inserted
Remaining: word1 stays, word2 moves forward
editDistance(i, j) = 1 + editDistance(i, j+1)
Take MINIMUM of all three choices!
editDistance(i, j) = 1 + min(
editDistance(i+1, j+1), // Replace
editDistance(i+1, j), // Delete
editDistance(i, j+1) // Insert
)
This is the complete recursive structure! ✓
Why Three Choices Make Sense
Let me understand WHY these three choices cover everything:
Example: word1 = "abc", word2 = "def"
At position 0: 'a' != 'd'
CHOICE 1: REPLACE 'a' with 'd'
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Before: word1 = "abc", word2 = "def"
After: word1 = "dbc", word2 = "def"
Now: word1[0] == word2[0] ✓
Remaining: "bc" vs "ef"
This handles: current positions in BOTH strings
Move: i+1, j+1
CHOICE 2: DELETE from word1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Before: word1 = "abc", word2 = "def"
After: word1 = "bc", word2 = "def"
Now: 'a' is gone from word1
Remaining: "bc" vs "def"
This handles: remove from word1, keep word2 position
Move: i+1, j
CHOICE 3: INSERT into word1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Before: word1 = "abc", word2 = "def"
After: word1 = "dabc", word2 = "def"
Now: word1[0] == word2[0] ✓
Remaining: "abc" vs "ef"
This handles: add to word1, move word2 position
Move: i, j+1
INSIGHT:
Every possible transformation is covered!
These three operations are COMPLETE! ✓
🔴 Approach 1: Pure Recursion - Understanding the Pattern
The Recursive Logic
Let me write the recursive function:
editDistance(word1, word2, i, j):
BASE CASE 1: word1 exhausted
if i == len(word1):
return len(word2) - j // Insert remaining from word2
BASE CASE 2: word2 exhausted
if j == len(word2):
return len(word1) - i // Delete remaining from word1
RECURSIVE CASE 1: Characters match
if word1[i] == word2[j]:
return editDistance(i+1, j+1) // No operation needed
RECURSIVE CASE 2: Characters don't match
else:
// Try all three operations, take minimum
replaceOp = 1 + editDistance(i+1, j+1)
deleteOp = 1 + editDistance(i+1, j)
insertOp = 1 + editDistance(i, j+1)
return min(replaceOp, deleteOp, insertOp)
This is the complete algorithm! ✓
Visualizing The Recursion Tree
Example: word1 = "cat", word2 = "cut"
Let me trace the recursion:
editDistance(0,0)
word1[0]='c', word2[0]='c'
Match! No operation needed ✓
editDistance(1,1)
word1[1]='a', word2[1]='u'
Don't match! Try all three ↓
Replace(1) Delete(1) Insert(1)
editDist(2,2) editDist(2,1) editDist(1,2)
't' vs 't' 't' vs 'u' 'a' vs 't'
Match! ✓ No match No match
return 0 Try 3 ops Try 3 ops
Total: 1+0=1 ✓ 1+more 1+more
Best path: REPLACE 'a' with 'u' → Total: 1 operation ✓
Another example: word1 = "ab", word2 = "ba"
editDistance(0,0)
'a' != 'b'
Replace(1) Delete(1) Insert(1)
editDist(1,1) editDist(1,0) editDist(0,1)
'b' vs 'a' 'b' vs 'ba' 'ab' vs 'a'
No match More ops More ops
Try 3... needed needed
Following recursion tree, we find minimum = 2 operations
(Multiple valid solutions: replace both, or delete+insert)
Implementation
class Solution {
public int minDistance(String word1, String word2) {
return editDistanceHelper(word1, word2, 0, 0);
}
private int editDistanceHelper(String word1, String word2, int i, int j) {
// Base case: word1 exhausted
if (i == word1.length()) {
return word2.length() - j;
}
// Base case: word2 exhausted
if (j == word2.length()) {
return word1.length() - i;
}
// Case 1: Characters match
if (word1.charAt(i) == word2.charAt(j)) {
return editDistanceHelper(word1, word2, i + 1, j + 1);
}
// Case 2: Characters don't match - try all three operations
int replaceOp = 1 + editDistanceHelper(word1, word2, i + 1, j + 1);
int deleteOp = 1 + editDistanceHelper(word1, word2, i + 1, j);
int insertOp = 1 + editDistanceHelper(word1, word2, i, j + 1);
return Math.min(replaceOp, Math.min(deleteOp, insertOp));
}
}
Why This Is Too Slow
TIME COMPLEXITY ANALYSIS:
At each non-matching position, we make 3 recursive calls!
Recursion tree branches exponentially!
(0,0)
/ | \
(1,1)(1,0)(0,1)
/|\ /|\ /|\
... many branches ...
↑ ↑
SAME STATE called MULTIPLE times!
Number of unique states: m × n
But each state called MANY times!
Worst case: O(3^(m+n)) ❌
For word1 = "abcdefgh" (8 chars)
word2 = "ijklmnop" (8 chars)
3^16 ≈ 43 million operations! ❌
OBSERVATION:
Same (i,j) computed multiple times!
Overlapping subproblems!
This screams MEMOIZATION! 🔑
🟡 Approach 2: Memoization (Top-Down DP)
Adding The Cache
The problem with pure recursion:
We solve same (i,j) many times!
Solution:
Cache the results!
memo[i][j] = minimum operations for editDistance(i, j)
When we compute editDistance(i, j):
1. Check if already computed (in memo)
2. If yes, return cached result (O(1)!)
3. If no, compute it, cache it, then return
This eliminates redundant computation! ✓
Why this works:
- Number of states: m × n
- Each state computed AT MOST once
- Total time: O(m × n) ✓
Much better than exponential! 🚀
Implementation
class Solution {
private Integer[][] memo;
public int minDistance(String word1, String word2) {
// Initialize memoization table
// Integer (not int) to distinguish uncomputed (null) vs computed
memo = new Integer[word1.length() + 1][word2.length() + 1];
return editDistanceHelper(word1, word2, 0, 0);
}
private int editDistanceHelper(String word1, String word2, int i, int j) {
// Check memo first
if (memo[i][j] != null) {
return memo[i][j];
}
// Base case: word1 exhausted
if (i == word1.length()) {
memo[i][j] = word2.length() - j;
return memo[i][j];
}
// Base case: word2 exhausted
if (j == word2.length()) {
memo[i][j] = word1.length() - i;
return memo[i][j];
}
int result;
// Case 1: Characters match
if (word1.charAt(i) == word2.charAt(j)) {
result = editDistanceHelper(word1, word2, i + 1, j + 1);
}
// Case 2: Characters don't match
else {
int replaceOp = 1 + editDistanceHelper(word1, word2, i + 1, j + 1);
int deleteOp = 1 + editDistanceHelper(word1, word2, i + 1, j);
int insertOp = 1 + editDistanceHelper(word1, word2, i, j + 1);
result = Math.min(replaceOp, Math.min(deleteOp, insertOp));
}
// Cache the result
memo[i][j] = result;
return result;
}
}
Why Memoization Works
KEY INSIGHT:
Number of unique states: m × n
(m = length of word1, n = length of word2)
Each state computed AT MOST ONCE!
When we see same (i,j) again:
Return cached result in O(1)!
TIME COMPLEXITY:
Number of states: O(m × n)
Work per state: O(1) operations
Total: O(m × n) ✓
SPACE COMPLEXITY:
Memo table: O(m × n)
Call stack: O(m + n)
Total: O(m × n) ✓
Much better than O(3^(m+n))! 🚀
🟢 Approach 3: Bottom-Up DP - Building From Base Cases
Understanding The DP State
Let me think about the DP table:
dp[i][j] = minimum operations to convert
word1[0..i-1] to word2[0..j-1]
What this means:
- word1[0..i-1] means first i characters of word1
- word2[0..j-1] means first j characters of word2
- dp[i][j] answers: minimum operations for these prefixes
Examples:
word1 = "cat", word2 = "cut"
dp[0][0] = convert "" to "" → 0 operations ✓
dp[1][1] = convert "c" to "c" → 0 operations ✓
dp[2][2] = convert "ca" to "cu" → 1 operation (replace 'a')
dp[3][3] = convert "cat" to "cut" → (final answer)
This is our DP definition! ✓
Building The DP Table - Understanding Each Cell
Let me build for: word1 = "cat", word2 = "cut"
Table dimensions: (len(word1)+1) × (len(word2)+1) = 4 × 4
Initial state:
"" c u t
"" ? ? ? ?
c ? ? ? ?
a ? ? ? ?
t ? ? ? ?
PHASE 1: Base Cases
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
dp[0][0]: Convert "" to ""
Both empty → 0 operations ✓
dp[0][0] = 0
dp[0][j]: Convert "" to word2[0..j-1]
Empty string to non-empty
Need to INSERT all characters from word2
dp[0][1]: "" to "c" → INSERT 'c' → 1 operation
dp[0][2]: "" to "cu" → INSERT 'c', INSERT 'u' → 2 operations
dp[0][3]: "" to "cut" → INSERT 'c', 'u', 't' → 3 operations
Pattern: dp[0][j] = j
"" c u t
"" 0 1 2 3
c ? ? ? ?
a ? ? ? ?
t ? ? ? ?
dp[i][0]: Convert word1[0..i-1] to ""
Non-empty string to empty
Need to DELETE all characters from word1
dp[1][0]: "c" to "" → DELETE 'c' → 1 operation
dp[2][0]: "ca" to "" → DELETE 'c', 'a' → 2 operations
dp[3][0]: "cat" to "" → DELETE 'c', 'a', 't' → 3 operations
Pattern: dp[i][0] = i
"" c u t
"" 0 1 2 3
c 1 ? ? ?
a 2 ? ? ?
t 3 ? ? ?
PHASE 2: Fill The Table
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Now fill dp[i][j] for i > 0, j > 0
dp[1][1]: Convert "c" to "c"
word1[0]='c', word2[0]='c' → Match! ✓
No operation needed!
dp[1][1] = dp[0][0] = 0
"" c u t
"" 0 1 2 3
c 1 0 ? ?
a 2 ? ? ?
t 3 ? ? ?
dp[1][2]: Convert "c" to "cu"
word1[0]='c', word2[1]='u' → Don't match ✗
Three choices:
Replace: 'c' → 'u', then "" to "c"
= 1 + dp[0][1] = 1 + 1 = 2
Delete: remove 'c', then "" to "cu"
= 1 + dp[0][2] = 1 + 2 = 3
Insert: add 'u', then "c" to "c"
= 1 + dp[1][1] = 1 + 0 = 1 ✓
Minimum: 1
dp[1][2] = 1
"" c u t
"" 0 1 2 3
c 1 0 1 ?
a 2 ? ? ?
t 3 ? ? ?
dp[1][3]: Convert "c" to "cut"
word1[0]='c', word2[2]='t' → Don't match ✗
Three choices:
Replace: 1 + dp[0][2] = 1 + 2 = 3
Delete: 1 + dp[0][3] = 1 + 3 = 4
Insert: 1 + dp[1][2] = 1 + 1 = 2 ✓
Minimum: 2
dp[1][3] = 2
"" c u t
"" 0 1 2 3
c 1 0 1 2
a 2 ? ? ?
t 3 ? ? ?
dp[2][1]: Convert "ca" to "c"
word1[1]='a', word2[0]='c' → Don't match ✗
Three choices:
Replace: 1 + dp[1][0] = 1 + 1 = 2
Delete: 1 + dp[1][1] = 1 + 0 = 1 ✓
Insert: 1 + dp[2][0] = 1 + 2 = 3
Minimum: 1
dp[2][1] = 1
"" c u t
"" 0 1 2 3
c 1 0 1 2
a 2 1 ? ?
t 3 ? ? ?
dp[2][2]: Convert "ca" to "cu"
word1[1]='a', word2[1]='u' → Don't match ✗
Three choices:
Replace: 1 + dp[1][1] = 1 + 0 = 1 ✓
Delete: 1 + dp[1][2] = 1 + 1 = 2
Insert: 1 + dp[2][1] = 1 + 1 = 2
Minimum: 1
dp[2][2] = 1
"" c u t
"" 0 1 2 3
c 1 0 1 2
a 2 1 1 ?
t 3 ? ? ?
dp[2][3]: Convert "ca" to "cut"
word1[1]='a', word2[2]='t' → Don't match ✗
Three choices:
Replace: 1 + dp[1][2] = 1 + 1 = 2 ✓
Delete: 1 + dp[1][3] = 1 + 2 = 3
Insert: 1 + dp[2][2] = 1 + 1 = 2 ✓
Minimum: 2
dp[2][3] = 2
"" c u t
"" 0 1 2 3
c 1 0 1 2
a 2 1 1 2
t 3 ? ? ?
dp[3][1]: Convert "cat" to "c"
word1[2]='t', word2[0]='c' → Don't match ✗
Three choices:
Replace: 1 + dp[2][0] = 1 + 2 = 3
Delete: 1 + dp[2][1] = 1 + 1 = 2 ✓
Insert: 1 + dp[3][0] = 1 + 3 = 4
Minimum: 2
dp[3][1] = 2
"" c u t
"" 0 1 2 3
c 1 0 1 2
a 2 1 1 2
t 3 2 ? ?
dp[3][2]: Convert "cat" to "cu"
word1[2]='t', word2[1]='u' → Don't match ✗
Three choices:
Replace: 1 + dp[2][1] = 1 + 1 = 2 ✓
Delete: 1 + dp[2][2] = 1 + 1 = 2 ✓
Insert: 1 + dp[3][1] = 1 + 2 = 3
Minimum: 2
dp[3][2] = 2
"" c u t
"" 0 1 2 3
c 1 0 1 2
a 2 1 1 2
t 3 2 2 ?
dp[3][3]: Convert "cat" to "cut"
word1[2]='t', word2[2]='t' → Match! ✓
No operation needed!
dp[3][3] = dp[2][2] = 1
"" c u t
"" 0 1 2 3
c 1 0 1 2
a 2 1 1 2
t 3 2 2 1
FINAL ANSWER: dp[3][3] = 1 ✓
Minimum operations to convert "cat" to "cut" = 1!
(REPLACE 'a' with 'u')
The DP Recurrence - Complete Understanding
For dp[i][j], we're asking:
Minimum operations to convert word1[0..i-1] to word2[0..j-1]?
CASE 1: Characters match
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
word1[i-1] == word2[j-1]
Characters are the same! No operation needed!
dp[i][j] = dp[i-1][j-1]
Example: "cat" vs "cut", last chars 't' == 't'
dp[3][3] = dp[2][2] (no operation for 't')
CASE 2: Characters don't match
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
word1[i-1] != word2[j-1]
Need an operation! Three choices:
Choice A: REPLACE word1[i-1] with word2[j-1]
Cost: 1 operation
After: both characters match
Remaining: solve for prefixes without these chars
dp[i][j] = 1 + dp[i-1][j-1]
Example: "ca" vs "cu", replace 'a' with 'u'
Then solve "c" vs "c"
Choice B: DELETE word1[i-1]
Cost: 1 operation
After: word1[i-1] is removed
Remaining: word1 is shorter, word2 stays same
dp[i][j] = 1 + dp[i-1][j]
Example: "ca" vs "c", delete 'a'
Then solve "c" vs "c"
Choice C: INSERT word2[j-1] into word1
Cost: 1 operation
After: word1 now has word2[j-1]
Remaining: word1 stays, word2 is shorter
dp[i][j] = 1 + dp[i][j-1]
Example: "c" vs "cu", insert 'u'
Then solve "c" vs "c"
Take MINIMUM:
dp[i][j] = 1 + min(
dp[i-1][j-1], // Replace
dp[i-1][j], // Delete
dp[i][j-1] // Insert
)
This is the complete DP recurrence! ✓
Why Forward Loops?
DEPENDENCY ANALYSIS:
dp[i][j] depends on:
- dp[i-1][j-1] (diagonal - one less from both)
- dp[i-1][j] (up - one less from word1)
- dp[i][j-1] (left - one less from word2)
All dependencies have SMALLER indices!
Visual:
j-1 j
i-1 [X] [X]
↓ ↓ ↘
i [X] [i,j]
All arrows point to smaller indices!
Therefore: Fill table with FORWARD loops!
for i from 0 to m:
for j from 0 to n:
compute dp[i][j]
Dependencies are already computed! ✓
Complete Implementation
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
// dp[i][j] = min operations to convert word1[0..i-1] to word2[0..j-1]
int[][] dp = new int[m + 1][n + 1];
// Base case: convert empty string to word2
for (int j = 0; j <= n; j++) {
dp[0][j] = j; // Insert j characters
}
// Base case: convert word1 to empty string
for (int i = 0; i <= m; i++) {
dp[i][0] = i; // Delete i characters
}
// Fill the table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
// Characters match - no operation needed
dp[i][j] = dp[i - 1][j - 1];
} else {
// Characters don't match - try all three operations
int replaceOp = dp[i - 1][j - 1]; // Replace
int deleteOp = dp[i - 1][j]; // Delete
int insertOp = dp[i][j - 1]; // Insert
dp[i][j] = 1 + Math.min(replaceOp, Math.min(deleteOp, insertOp));
}
}
}
return dp[m][n];
}
}
🔍 Detailed Example - Complete Walkthrough
Example: word1 = "horse", word2 = "ros"
Let me build the complete DP table!
m = 5 (horse), n = 3 (ros)
Table dimensions: 6 × 4
PHASE 1: Initialize Base Cases
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
"" r o s
"" 0 1 2 3
h 1 ? ? ?
o 2 ? ? ?
r 3 ? ? ?
s 4 ? ? ?
e 5 ? ? ?
PHASE 2: Fill Row By Row
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ROW 1 (i=1, word1="h"):
dp[1][1]: "h" to "r"
'h' != 'r' → min(1+dp[0][0], 1+dp[0][1], 1+dp[1][0])
= min(1+0, 1+1, 1+1) = 1 ✓
dp[1][2]: "h" to "ro"
'h' != 'o' → min(1+dp[0][1], 1+dp[0][2], 1+dp[1][1])
= min(1+1, 1+2, 1+1) = 2 ✓
dp[1][3]: "h" to "ros"
'h' != 's' → min(1+dp[0][2], 1+dp[0][3], 1+dp[1][2])
= min(1+2, 1+3, 1+2) = 3 ✓
"" r o s
"" 0 1 2 3
h 1 1 2 3
o 2 ? ? ?
r 3 ? ? ?
s 4 ? ? ?
e 5 ? ? ?
ROW 2 (i=2, word1="ho"):
dp[2][1]: "ho" to "r"
'o' != 'r' → min(1+dp[1][0], 1+dp[1][1], 1+dp[2][0])
= min(1+1, 1+1, 1+2) = 2 ✓
dp[2][2]: "ho" to "ro"
'o' == 'o' → Match! ✓
dp[2][2] = dp[1][1] = 1
dp[2][3]: "ho" to "ros"
'o' != 's' → min(1+dp[1][2], 1+dp[1][3], 1+dp[2][2])
= min(1+2, 1+3, 1+1) = 2 ✓
"" r o s
"" 0 1 2 3
h 1 1 2 3
o 2 2 1 2
r 3 ? ? ?
s 4 ? ? ?
e 5 ? ? ?
ROW 3 (i=3, word1="hor"):
dp[3][1]: "hor" to "r"
'r' == 'r' → Match! ✓
dp[3][1] = dp[2][0] = 2
dp[3][2]: "hor" to "ro"
'r' != 'o' → min(1+dp[2][1], 1+dp[2][2], 1+dp[3][1])
= min(1+2, 1+1, 1+2) = 2 ✓
dp[3][3]: "hor" to "ros"
'r' != 's' → min(1+dp[2][2], 1+dp[2][3], 1+dp[3][2])
= min(1+1, 1+2, 1+2) = 2 ✓
"" r o s
"" 0 1 2 3
h 1 1 2 3
o 2 2 1 2
r 3 2 2 2
s 4 ? ? ?
e 5 ? ? ?
ROW 4 (i=4, word1="hors"):
dp[4][1]: "hors" to "r"
's' != 'r' → min(1+dp[3][0], 1+dp[3][1], 1+dp[4][0])
= min(1+3, 1+2, 1+4) = 3 ✓
dp[4][2]: "hors" to "ro"
's' != 'o' → min(1+dp[3][1], 1+dp[3][2], 1+dp[4][1])
= min(1+2, 1+2, 1+3) = 3 ✓
dp[4][3]: "hors" to "ros"
's' == 's' → Match! ✓
dp[4][3] = dp[3][2] = 2
"" r o s
"" 0 1 2 3
h 1 1 2 3
o 2 2 1 2
r 3 2 2 2
s 4 3 3 2
e 5 ? ? ?
ROW 5 (i=5, word1="horse"):
dp[5][1]: "horse" to "r"
'e' != 'r' → min(1+dp[4][0], 1+dp[4][1], 1+dp[5][0])
= min(1+4, 1+3, 1+5) = 4 ✓
dp[5][2]: "horse" to "ro"
'e' != 'o' → min(1+dp[4][1], 1+dp[4][2], 1+dp[5][1])
= min(1+3, 1+3, 1+4) = 4 ✓
dp[5][3]: "horse" to "ros"
'e' != 's' → min(1+dp[4][2], 1+dp[4][3], 1+dp[5][2])
= min(1+3, 1+2, 1+4) = 3 ✓
"" r o s
"" 0 1 2 3
h 1 1 2 3
o 2 2 1 2
r 3 2 2 2
s 4 3 3 2
e 5 4 4 3
FINAL ANSWER: dp[5][3] = 3 ✓
Minimum operations to convert "horse" to "ros" = 3!
One possible sequence:
horse → rorse (replace 'h' with 'r')
rorse → rose (delete 'r')
rose → ros (delete 'e')
📊 Complexity Analysis
All Approaches Compared
┌──────────────┬─────────────┬──────────────┬──────────────┐
│ Approach │ Time │ Space │ Practical? │
├──────────────┼─────────────┼──────────────┼──────────────┤
│ Recursion │ O(3^(m+n)) │ O(m+n) │ NO ❌ │
│ (Approach 1) │ Exponential │ Stack │ Too slow │
├──────────────┼─────────────┼──────────────┼──────────────┤
│ Memoization │ O(m×n) │ O(m×n) │ YES ✓ │
│ (Approach 2) │ Polynomial │ Memo+Stack │ Good │
├──────────────┼─────────────┼──────────────┼──────────────┤
│ Bottom-Up DP │ O(m×n) │ O(m×n) │ YES ✓ │
│ (Approach 3) │ Polynomial │ Table only │ Best │
└──────────────┴─────────────┴──────────────┴──────────────┘
m = length of word1
n = length of word2
Detailed Time Complexity
APPROACH 1 - Pure Recursion:
At each non-matching position:
Three choices (replace, delete, insert)
Three recursive calls
Branching factor: 3
Tree height: m + n
Total nodes: O(3^(m+n)) ❌
For word1 = "abcdefgh" (8 chars)
word2 = "ijklmnop" (8 chars)
3^16 ≈ 43 million calls! ❌
APPROACH 2 - Memoization:
Number of unique states: m × n
Each state computed once: O(1) work
Total: O(m × n) ✓
For word1 = 100 chars, word2 = 100 chars:
100 × 100 = 10,000 states ✓
APPROACH 3 - Bottom-Up DP:
Nested loops: i from 0 to m, j from 0 to n
Each cell: O(1) work (three comparisons, one min)
Total: O(m × n) ✓
Same as memoization! ✓
Detailed Space Complexity
APPROACH 1 - Pure Recursion:
Call stack depth: O(m + n)
No extra storage
Total: O(m + n)
But impractical due to time! ❌
APPROACH 2 - Memoization:
Memo table: (m+1) × (n+1) integers
Size: O(m × n)
Call stack: O(m + n)
Total: O(m × n) ✓
APPROACH 3 - Bottom-Up DP:
DP table: (m+1) × (n+1) integers
Size: O(m × n)
No recursion stack!
Total: O(m × n) ✓
SPACE OPTIMIZATION:
Can we use O(n) space?
YES! Only need previous row!
int[] prev = new int[n+1];
int[] curr = new int[n+1];
For each i:
Compute curr from prev
prev = curr
Space: O(min(m,n)) ✓
But loses table for traceback
For interviews: O(m × n) is clearer! ✓
🎯 Pattern Recognition
The Edit Distance Family
EDIT DISTANCE VARIATIONS:
All measure string similarity through transformations!
1. Problem 245: Edit Distance (Levenshtein)
Operations: insert, delete, replace
All cost: 1 operation
This problem! ✓
2. Longest Common Subsequence (Problem 241):
Special case of edit distance!
Only insert and delete allowed
editDistance = m + n - 2×LCS
3. Delete Operations (Problem 239):
Another special case!
Only delete allowed
editDistance = m + n - 2×LCS
4. One Edit Distance (Problem 161):
Question: Are strings ONE edit apart?
Similar logic, simpler problem
5. Edit Distance with Costs:
Different costs for operations
Same DP structure, different values!
Common pattern:
- String transformation
- Multiple operations
- Find minimum
- DP solution! 🔑
Connection to Other String DP Problems
STRING DP PROBLEM FAMILY:
Problem 239: Delete Operations
→ Only deletions
→ Use LCS to minimize
Problem 240: Shortest Supersequence
→ Build string containing both
→ Use LCS to share characters
Problem 243: Regular Expression Matching
→ Pattern matching with '.', '*'
→ DP with choices
Problem 244: Wildcard Matching
→ Pattern matching with '?', '*'
→ Similar to regex
Problem 245: Edit Distance
→ Transform one to another
→ Three operations
→ Most general transformation! ✓
All share:
- Two strings
- Character-by-character decisions
- Overlapping subproblems
- DP table solution
- O(m × n) complexity
Edit Distance is the MOST GENERAL! 🔑
When To Recognize This Pattern
TRIGGER WORDS:
✓ "Minimum operations"
✓ "Transform/convert string"
✓ "Edit distance"
✓ "String similarity"
✓ "Insert/delete/replace"
PROBLEM STRUCTURE:
- Two strings
- Need transformation
- Multiple operation types
- Find minimum cost
SOLUTION APPROACH:
1. Define state: dp[i][j]
2. Base cases: empty strings
3. Recurrence: match vs operations
4. Fill table forward
5. Return dp[m][n]
This is a MASTER PATTERN! ✓
💻 Complete Working Code
class Solution {
// Approach 3: Bottom-Up DP (Most efficient)
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
// Base cases
for (int j = 0; j <= n; j++) {
dp[0][j] = j; // Insert j chars
}
for (int i = 0; i <= m; i++) {
dp[i][0] = i; // Delete i chars
}
// Fill table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
// Match - no operation
dp[i][j] = dp[i - 1][j - 1];
} else {
// Don't match - try all three operations
int replace = dp[i - 1][j - 1]; // Replace
int delete = dp[i - 1][j]; // Delete
int insert = dp[i][j - 1]; // Insert
dp[i][j] = 1 + Math.min(replace, Math.min(delete, insert));
}
}
}
return dp[m][n];
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.minDistance("horse", "ros")); // 3
System.out.println(sol.minDistance("intention", "execution")); // 5
System.out.println(sol.minDistance("cat", "cut")); // 1
}
}
🔑 Key Insights Summary
The Learning Journey
CRAWL (Understanding):
✓ What are the three operations?
✓ Why is transformation hard?
✓ Understanding choices at each step
✓ Why we need minimum
WALK (Building):
✓ Recursive structure
✓ Base cases (empty strings)
✓ Two main cases (match vs operations)
✓ Adding memoization
RUN (Mastery):
✓ Bottom-up DP
✓ Complete table construction
✓ Cell-by-cell understanding
✓ Pattern recognition
✓ Connection to LCS
Natural baby-to-expert progression! 🎯
The Core Understanding
1. WHY three operations?
They cover ALL transformations!
Insert: add characters
Delete: remove characters
Replace: change characters
2. WHAT is the recurrence?
Match: dp[i-1][j-1]
No match: 1 + min(three operations)
3. HOW to choose operation?
Try all three, take minimum!
DP tries all possibilities efficiently!
4. WHEN do chars match?
word1[i-1] == word2[j-1]
No operation needed! ✓
5. WHERE are dependencies?
dp[i-1][j-1], dp[i-1][j], dp[i][j-1]
All smaller indices!
Mental Model
Think of it as PATH FINDING:
From word1 to word2:
Many possible transformation paths
Each operation has cost 1
Find shortest path!
DP explores all paths efficiently:
Stores minimum cost to reach each state
Reuses solutions for subproblems
Visual:
word1 → operations → operations → word2
↓ ↓
many choices
paths everywhere
DP finds minimum path! ✓
📝 Quick Revision
🎯 Core Operations
INSERT → add character to word1
DELETE → remove character from word1
REPLACE → change character in word1
⚡ Quick Implementation
public class Solution {
public int minDistance(String s1, String s2) {
// return recursive(s1, s2, 0, 0);
// Integer[][] memo = new Integer[s1.length() + 1][s2.length() + 1];
// return topDown(s1, s2, 0, 0, memo);
return bottomUp(s1, s2);
}
private int bottomUp(String s1, String s2) {
int[][] dp = new int[s1.length() + 1][s2.length() + 1];
// step 2: base case 1 (empty s1)
for (int j = 1; j <= s2.length(); j++) {
dp[0][j] = j;
}
// step 3: base case 2 (empty s2)
for (int i = 1; i <= s1.length(); i++) {
dp[i][0] = i;
}
// step 1: exactly same as recursive or top down
for (int i = 1; i <= s1.length(); i++) {
for (int j = 1; j <= s2.length(); j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
} else {
int insert = dp[i][j - 1];
int delete = dp[i - 1][j];
int replace = dp[i - 1][j - 1];
dp[i][j] = 1 + Math.min(insert, Math.min(delete, replace));
}
}
}
return dp[s1.length()][s2.length()];
}
private int topDown(String s1, String s2, int i, int j, Integer[][] memo) {
if (i == s1.length()) {
return s2.length() - j;
}
if (j == s2.length()) {
return s1.length() - i;
}
if (memo[i][j] != null) {
return memo[i][j];
}
if (s1.charAt(i) == s2.charAt(j)) {
return memo[i][j] = recursive(s1, s2, i + 1, j + 1);
}
int insert = recursive(s1, s2, i, j + 1);
int delete = recursive(s1, s2, i + 1, j);
int replace = recursive(s1, s2, i + 1, j + 1);
return memo[i][j] = 1 + Math.min(insert, Math.min(delete, replace));
}
private int recursive(String s1, String s2, int i, int j) {
// step 3: base case 1 - s1 exhausted
if (i == s1.length()) {
return s2.length() - j;
}
// step 4: base case 2 - s2 exhausted
if (j == s2.length()) {
return s1.length() - i;
}
// step 1: if chars of s1 and s2 match, proceed to next chars
if (s1.charAt(i) == s2.charAt(j)) {
return recursive(s1, s2, i + 1, j + 1);
}
// step 2: insert or delete or replace a char on s1
int insert = recursive(s1, s2, i, j + 1);
int delete = recursive(s1, s2, i + 1, j);
int replace = recursive(s1, s2, i + 1, j + 1);
return 1 + Math.min(insert, Math.min(delete, replace));
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.minDistance("horse", "ros") == 3);
System.out.println(s.minDistance("intention", "execution") == 5);
}
}
🎪 Memory Aid
"Three choices when different"
"No choice when same"
"DP finds minimum path"
Complexity: O(m×n) time and space
🎉 Congratulations!
You've mastered through baby steps:
- ✅ CRAWL: Understanding edit operations
- ✅ WALK: Building recursive structure
- ✅ RUN: Complete DP mastery
- ✅ All three approaches explained
- ✅ Complete table walkthrough
- ✅ Connection to LCS and other problems
- ✅ Pattern recognition mastery
- ✅ True comprehensive understanding
The CLASSIC edit distance problem conquered with textbook-style learning! 🚀✨