239. Delete Operation for Two Strings
🔗 LeetCode Problem: 583. Delete Operation for Two Strings
📊 Difficulty: Medium
🏷️ Topics: Dynamic Programming, String, DP - Strings
Problem Statement
Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same.
In one step, you can delete exactly one character in either string.
Example 1:
Input: word1 = "sea", word2 = "eat"
Output: 2
Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea".
Example 2:
Input: word1 = "leetcode", word2 = "etco"
Output: 4
Constraints:
- 1 <= word1.length, word2.length <= 500
- word1 and word2 consist of only lowercase English letters.
🧒 Let's Build Understanding from Absolute Scratch
What Does This Problem REALLY Ask?
Forget "minimum steps" for a moment. Let's understand what we're doing:
Given: word1 = "sea", word2 = "eat"
Goal: Make them the SAME by ONLY deleting characters
Let me try:
word1 = "sea"
word2 = "eat"
They're different. What can we do?
Option 1: Delete from word1
Delete 's' from "sea" → "ea"
Now: word1="ea", word2="eat"
Still different!
Option 2: Delete from word2
Delete 't' from "eat" → "ea"
Now: word1="sea", word2="ea"
Still different!
Let me try BOTH:
Delete 's' from "sea" → "ea"
Delete 't' from "eat" → "ea"
Now: word1="ea", word2="ea"
SAME! ✓
Total deletions: 2 (one from each string)
So the answer is 2!
KEY INSIGHT: We're finding a common substring that's left after deletions!
The Hidden Pattern - What Are We REALLY Finding?
Let me think backwards:
word1 = "sea" → delete 's' → "ea"
word2 = "eat" → delete 't' → "ea"
Final result: "ea"
Question: What is "ea" in relation to "sea" and "eat"?
"ea" appears in BOTH strings in ORDER:
"sea" → s[e][a] → "ea" ✓
"eat" → [e][a]t → "ea" ✓
"ea" is a COMMON SUBSEQUENCE! 🎯
Wait... if we keep the LONGEST common subsequence,
we minimize deletions!
Example:
word1 = "sea" (length 3)
word2 = "eat" (length 3)
Longest common subsequence = "ea" (length 2)
Deletions from word1 = 3 - 2 = 1 (delete 's')
Deletions from word2 = 3 - 2 = 1 (delete 't')
Total = 1 + 1 = 2 ✓
EUREKA MOMENT:
Minimum deletions = (len(word1) - LCS) + (len(word2) - LCS)
= len(word1) + len(word2) - 2*LCS
We need to find the LONGEST COMMON SUBSEQUENCE! 🔑
🤔 Why Longest Common Subsequence? Let Me Prove It!
Understanding Through Examples
Example: word1 = "abc", word2 = "aec"
All common subsequences:
"a" → appears in both ✓
"c" → appears in both ✓
"ac" → appears in both ✓ (longest!)
If we keep "ac":
word1 = "abc" → delete 'b' → "ac" (1 deletion)
word2 = "aec" → delete 'e' → "ac" (1 deletion)
Total: 2 deletions ✓
If we keep "a" (shorter):
word1 = "abc" → delete 'b', 'c' → "a" (2 deletions)
word2 = "aec" → delete 'e', 'c' → "a" (2 deletions)
Total: 4 deletions ✗ (worse!)
INSIGHT: Longer common subsequence → fewer deletions!
We want the LONGEST one!
Why NOT Just Any Common String?
Question: Why subsequence? Why not just any common string?
word1 = "sea"
word2 = "eat"
Common characters: 'e', 'a'
Common string: "ea"
But why can't we rearrange?
Because DELETIONS preserve ORDER!
Example:
word1 = "sea" → delete 's' → "ea"
The order is maintained: 'e' comes before 'a'
We can't get "ae" by only deleting!
Deletion preserves relative positions! ✓
That's why we need SUBSEQUENCE (order matters)
not just common characters! 🔑
💡 Building the Solution Step by Step
Step 1: Reframe the Problem
ORIGINAL PROBLEM:
"Find minimum deletions to make word1 and word2 same"
REFRAMED PROBLEM:
"Find longest common subsequence (LCS)"
Then: deletions = len(word1) + len(word2) - 2*LCS
Why this helps?
LCS is a CLASSIC DP problem!
We can build on known techniques! ✓
Step 2: Understanding LCS with Examples
Let me trace LCS for "sea" and "eat":
word1 = "sea"
word2 = "eat"
Question: What's the longest subsequence common to both?
Try to match characters:
From word1="sea", word2="eat":
's' in word1: is 's' in word2? No ✗
'e' in word1: is 'e' in word2? Yes! ✓
'a' in word1: is 'a' in word2? Yes! ✓
Common: "ea" (length 2)
Can we find longer? No! ✓
LCS = "ea", length = 2
Deletions:
word1: len=3, keep 2, delete 3-2=1
word2: len=3, keep 2, delete 3-2=1
Total: 1+1 = 2 ✓
Step 3: How Do We FIND LCS?
This is where it gets interesting!
For "sea" and "eat", I found "ea" by inspection.
But what's the SYSTEMATIC approach?
Let me think recursively:
Compare first characters:
word1[0] = 's'
word2[0] = 'e'
Different! ✗
When first characters differ, we have TWO choices:
Choice 1: Skip first character of word1
Compare "ea" with "eat"
Choice 2: Skip first character of word2
Compare "sea" with "at"
Try BOTH, pick the better one!
This sounds RECURSIVE! 🎯
🎯 The Recursive Insight
Defining the Recursive Function
Let me define: LCS(i, j)
= "Longest common subsequence of word1[i...] and word2[j...]"
Starting from the BEGINNING of both strings:
Case 1: Characters match (word1[i] == word2[j])
Great! This character is PART of LCS!
LCS(i, j) = 1 + LCS(i+1, j+1)
Why +1? We found a matching character!
Why i+1, j+1? Move to next in both strings!
Case 2: Characters don't match (word1[i] != word2[j])
We must skip one! But which?
Option A: Skip word1[i], keep word2[j]
LCS(i+1, j)
Option B: Skip word2[j], keep word1[i]
LCS(i, j+1)
LCS(i, j) = max(Option A, Option B)
Why max? We want the LONGEST!
Base Cases:
If i == len(word1): reached end of word1 → return 0
If j == len(word2): reached end of word2 → return 0
This is BEAUTIFUL! 🌟
Let Me Trace This By Hand
word1 = "sea", word2 = "eat"
LCS(0, 0): word1[0]='s', word2[0]='e'
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Different! ✗
Option A: LCS(1, 0) → skip 's' from word1
Option B: LCS(0, 1) → skip 'e' from word2
Return max(Option A, Option B)
Let me follow Option A:
LCS(1, 0): word1[1]='e', word2[0]='e'
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Match! ✓
Return 1 + LCS(2, 1)
LCS(2, 1): word1[2]='a', word2[1]='a'
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Match! ✓
Return 1 + LCS(3, 2)
LCS(3, 2): i=3 == len(word1)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Reached end of word1!
Return 0
Backtrack:
LCS(2, 1) = 1 + 0 = 1
LCS(1, 0) = 1 + 1 = 2
So Option A gives 2!
Let me check Option B:
LCS(0, 1): word1[0]='s', word2[1]='a'
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Different! ✗
... (this will give less than 2)
So max(2, something_less) = 2!
LCS length = 2 ✓
Minimum deletions:
= 3 + 3 - 2*2
= 6 - 4
= 2 ✓
Perfect! The recursive logic works!
🔴 Approach 1: Pure Recursion (LCS-based)
Why This Approach First?
I'm showing recursion FIRST because:
1. It matches our THINKING process
We discovered the pattern recursively!
2. It's INTUITIVE
"If characters match, include it"
"If they don't, try skipping each"
3. Easy to understand
No tables, no loops, just logic!
Once we understand this, optimization is natural! ✓
The Implementation Logic
// Find LCS length
int lcs(String word1, String word2, int i, int j) {
// Base case: reached end of either string
if (i == word1.length() || j == word2.length()) {
return 0;
}
// Case 1: Characters match
if (word1.charAt(i) == word2.charAt(j)) {
return 1 + lcs(word1, word2, i+1, j+1);
}
// Case 2: Characters don't match - try both options
int skipWord1 = lcs(word1, word2, i+1, j);
int skipWord2 = lcs(word1, word2, i, j+1);
return Math.max(skipWord1, skipWord2);
}
// Main function
int minDistance(String word1, String word2) {
int lcsLength = lcs(word1, word2, 0, 0);
return word1.length() + word2.length() - 2*lcsLength;
}
Why This Is Slow
Time Complexity: O(2^(m+n))
Why exponential?
At each step with non-matching characters:
We make 2 recursive calls
Tree grows exponentially:
(0,0)
/ \
(1,0) (0,1)
/ \ / \
(2,0) (1,1) (1,1) (0,2)
↑ ↑
Same state called TWICE!
For m=n=20:
2^40 ≈ 1 trillion operations! ❌
INSIGHT: We're solving same (i,j) many times!
This screams MEMOIZATION! 🔑
🟡 Approach 2: Memoization (Top-Down DP)
The Reasoning Behind Memoization
OBSERVATION: Same subproblems solved repeatedly!
Example:
LCS(1, 1) might be called from:
- LCS(0, 0) → skip word1[0]
- LCS(0, 0) → skip word2[0]
Why compute it twice? Store it!
IDEA: Create a cache!
memo[i][j] = LCS of word1[i...] and word2[j...]
First time we compute LCS(i, j):
- Calculate the answer
- Store in memo[i][j]
Next time we need LCS(i, j):
- Check memo[i][j]
- Return immediately if found!
This is DYNAMIC PROGRAMMING! ✓
Why Memoization Works
Number of unique states: m × n
i can be 0 to m
j can be 0 to n
Total: m × n states
Each state computed ONCE:
First call: compute and cache
Later calls: return cached value
Time Complexity: O(m × n)
Each of m×n states computed once
Each computation: O(1)
Total: O(m × n) ✓
HUGE improvement: 2^40 → 400 for m=n=20! 🚀
The Implementation
class Solution {
private int[][] memo;
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
// Initialize memo with -1 (not computed)
memo = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
memo[i][j] = -1;
}
}
int lcsLength = lcs(word1, word2, 0, 0);
return m + n - 2*lcsLength;
}
private int lcs(String word1, String word2, int i, int j) {
// Base case
if (i == word1.length() || j == word2.length()) {
return 0;
}
// Check memo
if (memo[i][j] != -1) {
return memo[i][j];
}
// Compute
int result;
if (word1.charAt(i) == word2.charAt(j)) {
result = 1 + lcs(word1, word2, i+1, j+1);
} else {
int skip1 = lcs(word1, word2, i+1, j);
int skip2 = lcs(word1, word2, i, j+1);
result = Math.max(skip1, skip2);
}
// Cache and return
memo[i][j] = result;
return result;
}
}
🟢 Approach 3: Bottom-Up DP
Transitioning from Recursion to Iteration
RECURSIVE APPROACH:
Start from (0, 0)
Make recursive calls
Build answer from smaller problems
BOTTOM-UP APPROACH:
Compute smaller problems FIRST
Build up to the answer
No recursion needed!
How do we know what's "smaller"?
In recursion: LCS(i, j) calls LCS(i+1, ...) or LCS(..., j+1)
So (i+1, j+1) is "smaller" than (i, j)
In bottom-up: Compute larger i, j first!
Then work backwards to (0, 0)
Understanding the DP Table
Let's define: dp[i][j]
What should it represent?
Option A: LCS of word1[i...end] and word2[j...end]
This matches our recursion ✓
But requires reverse iteration...
Option B: LCS of word1[0...i-1] and word2[0...j-1]
This is more natural for forward iteration!
Standard in DP problems ✓
I'll use Option B for clarity!
dp[i][j] = LCS length of first i chars of word1
and first j chars of word2
The DP Recurrence
How do we fill dp[i][j]?
Think: We're comparing word1[0...i-1] with word2[0...j-1]
Case 1: Last characters match (word1[i-1] == word2[j-1])
Great! This character is part of LCS!
dp[i][j] = 1 + dp[i-1][j-1]
Why? If last chars match, LCS includes this character
Plus the LCS of the strings WITHOUT these chars!
Case 2: Last characters don't match
We skip one! But which?
Option A: Skip word1[i-1]
dp[i-1][j] (first i-1 of word1, first j of word2)
Option B: Skip word2[j-1]
dp[i][j-1] (first i of word1, first j-1 of word2)
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Base Cases:
dp[0][j] = 0 (no characters from word1 → LCS = 0)
dp[i][0] = 0 (no characters from word2 → LCS = 0)
Which Loop Direction?
DEPENDENCY ANALYSIS:
dp[i][j] needs:
- dp[i-1][j-1] (diagonal above-left)
- dp[i-1][j] (directly above)
- dp[i][j-1] (directly left)
Visual:
j-1 j
i-1 ↓ ↓
↘
i → [i,j]
Arrows point UP and LEFT!
Therefore:
- i should go FORWARD (need i-1 before i)
- j should go FORWARD (need j-1 before j)
LOOP PATTERN:
for (int i = 1; i <= m; i++) { // Forward ✓
for (int j = 1; j <= n; j++) { // Forward ✓
// Compute dp[i][j]
}
}
This is the STANDARD 2D DP pattern! ✓
Complete Implementation
class Solution {
public int minDistance(String word1, String word2) {
int m = word1.length();
int n = word2.length();
// dp[i][j] = LCS of first i chars of word1, first j chars of word2
int[][] dp = new int[m + 1][n + 1];
// Base cases: dp[0][j] = 0, dp[i][0] = 0 (already 0 by default)
// 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
dp[i][j] = 1 + dp[i-1][j-1];
} else {
// Characters don't match
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
int lcsLength = dp[m][n];
return m + n - 2*lcsLength;
}
}
Why Forward Loops Work Here
COMPARISON TO PROBLEM 238:
Problem 238 (Palindromic Subsequence):
dp[i][j] needs dp[i+1][...]
Needs LARGER i → use BACKWARD loop
This Problem (LCS):
dp[i][j] needs dp[i-1][...]
Needs SMALLER i → use FORWARD loop
RULE:
Access i-1? → i goes forward (0 to n)
Access i+1? → i goes backward (n to 0)
Same rule applies for j!
This problem: Access i-1 and j-1
→ Both loops FORWARD! ✓
🎨 Visual Example: Building the DP Table
word1 = "sea", word2 = "eat"
"" e a t
"" 0 0 0 0
s 0 ? ? ?
e 0 ? ? ?
a 0 ? ? ?
Fill row by row, left to right:
i=1, j=1: word1[0]='s', word2[0]='e'
Different → max(dp[0][1]=0, dp[1][0]=0) = 0
i=1, j=2: word1[0]='s', word2[1]='a'
Different → max(dp[0][2]=0, dp[1][1]=0) = 0
i=1, j=3: word1[0]='s', word2[2]='t'
Different → max(dp[0][3]=0, dp[1][2]=0) = 0
"" e a t
"" 0 0 0 0
s 0 0 0 0
e 0 ? ? ?
a 0 ? ? ?
i=2, j=1: word1[1]='e', word2[0]='e'
Match! ✓ → 1 + dp[1][0] = 1 + 0 = 1
i=2, j=2: word1[1]='e', word2[1]='a'
Different → max(dp[1][2]=0, dp[2][1]=1) = 1
i=2, j=3: word1[1]='e', word2[2]='t'
Different → max(dp[1][3]=0, dp[2][2]=1) = 1
"" e a t
"" 0 0 0 0
s 0 0 0 0
e 0 1 1 1
a 0 ? ? ?
i=3, j=1: word1[2]='a', word2[0]='e'
Different → max(dp[2][1]=1, dp[3][0]=0) = 1
i=3, j=2: word1[2]='a', word2[1]='a'
Match! ✓ → 1 + dp[2][1] = 1 + 1 = 2
i=3, j=3: word1[2]='a', word2[2]='t'
Different → max(dp[2][3]=1, dp[3][2]=2) = 2
"" e a t
"" 0 0 0 0
s 0 0 0 0
e 0 1 1 1
a 0 1 2 2
LCS length = dp[3][3] = 2 ✓
Minimum deletions:
= 3 + 3 - 2*2
= 6 - 4
= 2 ✓
🤔 Alternative Approach: Direct DP Without LCS
Can We Solve This WITHOUT Finding LCS First?
INTERESTING QUESTION!
Instead of:
1. Find LCS
2. Calculate deletions
Can we directly compute minimum deletions?
Let me think...
dp[i][j] = minimum deletions to make
word1[0...i-1] same as word2[0...j-1]
Case 1: word1[i-1] == word2[j-1]
Characters match! No deletion needed!
dp[i][j] = dp[i-1][j-1]
Why? If last chars are same, answer is same as
making the strings WITHOUT these chars equal!
Case 2: word1[i-1] != word2[j-1]
Characters differ! Must delete one!
Option A: Delete from word1
dp[i][j] = 1 + dp[i-1][j]
Option B: Delete from word2
dp[i][j] = 1 + dp[i][j-1]
dp[i][j] = min(option A, option B)
Base Cases:
dp[0][j] = j (delete all j characters from word2)
dp[i][0] = i (delete all i characters from word1)
This also works! ✓
Comparing Both Approaches
APPROACH 1 (LCS-based):
1. Find LCS length
2. deletions = m + n - 2*LCS
Pros: Reuses classic LCS algorithm
Cons: Indirect (two-step process)
APPROACH 2 (Direct):
1. Directly compute minimum deletions
Pros: Direct, one-step
Cons: Less obvious why it works
WHICH IS BETTER?
For learning: LCS-based! (connects to known patterns)
For coding: Direct! (simpler, fewer steps)
Both have SAME complexity: O(m × n)! ✓
💻 Complete Working Code
class Solution {
public int minDistance(String word1, String word2) {
// I'll show both approaches!
return directDP(word1, word2);
}
// Approach 1: LCS-based (Bottom-Up)
private int lcsBasedDP(String word1, String word2) {
int m = word1.length();
int n = word2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
int lcsLength = dp[m][n];
return m + n - 2 * lcsLength;
}
// Approach 2: Direct DP (Bottom-Up)
private int directDP(String word1, String word2) {
int m = word1.length();
int n = word2.length();
// dp[i][j] = min deletions for word1[0...i-1] and word2[0...j-1]
int[][] dp = new int[m + 1][n + 1];
// Base cases
for (int i = 0; i <= m; i++) {
dp[i][0] = i; // Delete all from word1
}
for (int j = 0; j <= n; j++) {
dp[0][j] = j; // Delete all from word2
}
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 deletion
dp[i][j] = dp[i - 1][j - 1];
} else {
// Delete from word1 or word2
dp[i][j] = 1 + Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
// Approach 3: Memoization (Top-Down LCS)
private int[][] memo;
private int memoization(String word1, String word2) {
int m = word1.length();
int n = word2.length();
memo = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
memo[i][j] = -1;
}
}
int lcsLength = lcs(word1, word2, 0, 0);
return m + n - 2 * lcsLength;
}
private int lcs(String word1, String word2, int i, int j) {
if (i == word1.length() || j == word2.length()) {
return 0;
}
if (memo[i][j] != -1) {
return memo[i][j];
}
int result;
if (word1.charAt(i) == word2.charAt(j)) {
result = 1 + lcs(word1, word2, i + 1, j + 1);
} else {
result = Math.max(lcs(word1, word2, i + 1, j), lcs(word1, word2, i, j + 1));
}
memo[i][j] = result;
return result;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.minDistance("sea", "eat") == 2);
System.out.println(s.minDistance("leetcode", "etco") == 4);
}
}
🔑 Deep Understanding - The WHY Behind Everything
Why Does LCS Give Minimum Deletions?
PROOF BY REASONING:
Given: word1 and word2
Goal: Make them equal by deletions
Key Insight: After deletions, what remains must be:
1. Present in BOTH original strings
2. In the SAME ORDER (deletions preserve order)
This is the DEFINITION of common subsequence! ✓
Question: Which common subsequence to keep?
If we keep LONGER subsequence:
→ Fewer deletions needed ✓
If we keep SHORTER subsequence:
→ More deletions needed ✗
Therefore: Keep the LONGEST common subsequence!
This MINIMIZES deletions! QED ✓
Why Does the Recurrence Work?
INDUCTIVE REASONING:
For dp[i][j] (LCS of first i and first j characters):
Case 1: Last characters match (word1[i-1] == word2[j-1])
Claim: dp[i][j] = 1 + dp[i-1][j-1]
Proof:
If last chars match, they SHOULD be in LCS!
Why? Suppose they're NOT in the optimal LCS.
Then LCS length = dp[i-1][j-1] or dp[i][j-1] or dp[i-1][j]
But we can ADD the matching character!
New LCS length = 1 + previous LCS
Contradiction! (we said it was optimal)
So they MUST be in optimal LCS!
LCS = matching char + LCS of remaining
dp[i][j] = 1 + dp[i-1][j-1] ✓
Case 2: Last characters don't match
Claim: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Proof:
If last chars don't match, at least ONE must be excluded!
Two scenarios:
A. Optimal LCS doesn't use word1[i-1]
→ LCS = LCS of word1[0...i-2] and word2[0...j-1]
→ dp[i-1][j]
B. Optimal LCS doesn't use word2[j-1]
→ LCS = LCS of word1[0...i-1] and word2[0...j-2]
→ dp[i][j-1]
We don't know which, so try BOTH!
Take the maximum! ✓
The recurrence is CORRECT by mathematical induction! ✓
Why Forward Loops?
DEPENDENCY REASONING:
dp[i][j] depends on:
- dp[i-1][j-1]
- dp[i-1][j]
- dp[i][j-1]
For these to be available when computing dp[i][j]:
- i-1 < i → need to compute smaller i FIRST
- j-1 < j → need to compute smaller j FIRST
Therefore:
- i must go from 0 → m (forward)
- j must go from 0 → n (forward)
Any other order would access uncomputed values! ✗
Forward loops are NOT just convention,
they're NECESSARY for correctness! ✓
🎯 Pattern Recognition
This Problem Belongs to a Family
COMMON PATTERN: Edit Distance Family
All these problems ask:
"Transform string A to string B using operations"
Problem 1: Minimum Deletions (this problem)
Operations: Delete from either string
Problem 2: Edit Distance (Levenshtein)
Operations: Insert, delete, replace
Problem 3: Minimum Insertions to Make Palindrome
Operations: Insert only
All solved with SAME DP approach!
dp[i][j] = cost to transform word1[0...i] to word2[0...j]
Key insight: Each operation has a recurrence!
The Template
GENERAL TEMPLATE:
dp[i][j] = transform cost for first i of word1, first j of word2
Base cases:
dp[0][j] = cost to get word2[0...j] from empty string
dp[i][0] = cost to get empty string from word1[0...i]
Recurrence:
if (word1[i-1] == word2[j-1]):
dp[i][j] = dp[i-1][j-1] // No operation needed
else:
dp[i][j] = min/max of possible operations
This template works for MANY problems! 🔑
📝 Quick Revision Notes
🎯 Core Insight
Problem: Minimum deletions to make two strings equal
Key Realization: Result must be a common subsequence
Optimization: Keep LONGEST common subsequence
Formula: deletions = m + n - 2×LCS
⚡ The Recurrence
public class Solution {
public int minDistance(String s1, String s2) {
// Approach - LCS
// for "leetcode" and "etco", len(LCS) = 4
// res = len("leetcode")+len("etco")-2*len(LCS)=8+4-8=4
int len1 = s1.length();
int len2 = s2.length();
// int lcs = recursive(s1, s2, 0, 0);
// Integer[][] memo = new Integer[len1 + 1][len2 + 1];
// int lcs = topDown(s1, s2, 0, 0, memo);
int lcs = bottomUp(s1, s2);
return len1 + len2 - 2 * lcs;
}
private int bottomUp(String s1, String s2) {
int len1 = s1.length();
int len2 = s2.length();
int[][] dp = new int[len1 + 1][len2 + 1];
for (int i = 1; i <= len1; i++) {
for (int j = 1; j <= len2; j++) {
if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
// step 2: skip char at i
int option1 = dp[i - 1][j];
// step 3: skip char at j
int option2 = dp[i][j - 1];
dp[i][j] = Math.max(option1, option2);
}
}
}
return dp[len1][len2];
}
private int topDown(String s1, String s2, int i, int j, Integer[][] memo) {
// step 4a: base case 1
if (i == s1.length() && j == s2.length()) {
return 0;
}
// step 4b: base case 2
if (i >= s1.length() || j >= s2.length()) {
return Integer.MIN_VALUE;
}
if (memo[i][j] != null) {
return memo[i][j];
}
// step 1: current chars matched. Proceed with next chars
if (s1.charAt(i) == s2.charAt(j)) {
return 1 + topDown(s1, s2, i + 1, j + 1, memo);
}
// step 2: skip char at i
int option1 = topDown(s1, s2, i + 1, j, memo);
// step 3: skip char at j
int option2 = topDown(s1, s2, i, j + 1, memo);
return memo[i][j] = Math.max(option1, option2);
}
private int recursive(String s1, String s2, int i, int j) {
// step 4a: base case 1
if (i == s1.length() && j == s2.length()) {
return 0;
}
// step 4b: base case 2
if (i >= s1.length() || j >= s2.length()) {
return Integer.MIN_VALUE;
}
// step 1: current chars matched. Proceed with next chars
if (s1.charAt(i) == s2.charAt(j)) {
return 1 + recursive(s1, s2, i + 1, j + 1);
}
// step 2: skip char at i
int option1 = recursive(s1, s2, i + 1, j);
// step 3: skip char at j
int option2 = recursive(s1, s2, i, j + 1);
return Math.max(option1, option2);
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.minDistance("sea", "eat") == 2);
System.out.println(s.minDistance("leetcode", "etco") == 4);
}
}
Complexity: O(m×n) time and space
🎉 Congratulations!
You've learned through: - ✅ Deep reasoning WHY we need LCS - ✅ Mathematical proof of correctness - ✅ Understanding loop directions - ✅ Two valid approaches (LCS vs Direct) - ✅ Pattern recognition for similar problems
Pure reasoning-based learning! 🚀✨