LeetCode · #72

Edit Distance Solution

Given two strings, return the minimum number of insert, delete, or replace operations to convert one into the other.

Section One · Problem

Problem Statement

🏷️

Difficulty

Hard

🔗

LeetCode

Problem #72

🏗️

Pattern

DP — 2D edit distance (Levenshtein)

Given two strings word1 and word2, return the minimum number of operations (insert, delete, replace a character) to convert word1 into word2.

Example

Input: word1 = "horse", word2 = "ros" Output: 3 // horse → rorse (replace h→r) → rose (delete r) → ros (delete e)

Constraints

• 0 ≤ word1.length, word2.length ≤ 500

Section Two · Approach 1

Recursion — O(3^(m+n))

At each pair (i,j), if characters match, move both pointers. Otherwise, try all three operations and take the minimum: insert (advance j), delete (advance i), replace (advance both).

Why it works

Exhaustively tries all operation sequences. Minimum across all paths is the answer.

Why we can do better

Problem: Overlapping subproblems. Each (i,j) pair is recomputed. 2D DP table stores each once: O(m·n).

Java — Recursive

 class Solution {
public int minDistance(String w1, String w2) {
return dp(w1, w2, w1.length(), w2.length());
    }
private int dp(String a, String b, int i, int j) {
if (i == 0) return j; // insert remaining j chars if (j == 0) return i; // delete remaining i chars if (a.charAt(i-1) == b.charAt(j-1))
return dp(a, b, i-1, j-1);
return 1 + Math.min(dp(a,b,i,j-1), // insert
Math.min(dp(a,b,i-1,j), // delete dp(a,b,i-1,j-1))); // replace
}
}

Python — Recursive

 class Solution:
def minDistance(self, w1: str, w2: str) -> int:
def dp(i, j):
if i == 0: return j
if j == 0: return i
if w1[i-1] == w2[j-1]: return dp(i-1, j-1)
return 1 + min(dp(i,j-1), dp(i-1,j), dp(i-1,j-1))
return dp(len(w1), len(w2))

Metric	Value
Time	O(3^max(m,n))
Space	O(m+n)

Section Three · Approach 2

2D DP — O(m·n)

dp[i][j] = min operations to convert word1[0..i-1] to word2[0..j-1]. If characters match: dp[i-1][j-1] (no cost). Else: 1 + min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]).

💡 Mental model: Imagine you're a copy editor with three tools: a pen (replace a letter), scissors (delete), and a stamp (insert). You read both words left to right. When letters match, you move on for free. When they differ, you pick the cheapest tool. The grid records the minimum edits needed at each alignment point — each cell asks "what's the cheapest way to match these prefixes?"

Algorithm

Base cases: dp[i][0] = i (delete all of word1), dp[0][j] = j (insert all of word2).
Fill row by row. Match → diagonal (free). Mismatch → 1 + min of three neighbors.
Return dp[m][n].

🎯 When to recognize this pattern: "Minimum operations to transform one string into another." This is THE classic edit distance (Levenshtein distance) problem. Used in spell checkers, DNA alignment, and diff tools. Related: LC 583 (Delete Operations — only deletes), LC 1143 (LCS — edit distance without replace).

Three operations map to three neighbors: Insert = dp[i][j-1] (word2 advances, word1 stays — we "inserted" the needed character). Delete = dp[i-1][j] (word1 advances, word2 stays — we deleted a character). Replace = dp[i-1][j-1] (both advance — we changed the character).

Section Four · Trace

Visual Walkthrough

Trace for word1="horse", word2="ros".

Edit Distance — 2D DP

Section Five · Implementation

Code — Java & Python

Java — 2D DP

 class Solution {
public int minDistance(String w1, String w2) {
int m = w1.length(), n = w2.length();
int[][] dp = new int[m+1][n+1];
for (int i = 0; i <= m; i++) dp[i][0] = i;
for (int j = 0; j <= n; j++) dp[0][j] = j;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
                dp[i][j] = w1.charAt(i-1) == w2.charAt(j-1)
                    ? dp[i-1][j-1]
                    : 1 + Math.min(dp[i-1][j-1],
                          Math.min(dp[i-1][j], dp[i][j-1]));
return dp[m][n];
    }
}

Python — 2D DP

 class Solution:
def minDistance(self, w1: str, w2: str) -> int:
        m, n = len(w1), len(w2)
        dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(m+1): dp[i][0] = i
for j in range(n+1): dp[0][j] = j
for i in range(1, m+1):
for j in range(1, n+1):
if w1[i-1] == w2[j-1]:
                    dp[i][j] = dp[i-1][j-1]
else:
                    dp[i][j] = 1 + min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])
return dp[m][n]

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
Recursion	O(3^max(m,n))	O(m+n)	Exponential
Memoized recursion	O(m·n)	O(m·n)	Top-down
2D DP ← optimal	O(m·n)	O(m·n)	Can optimize to O(min(m,n)) space

Edit Distance is foundational: It's used in spell checkers, DNA sequence alignment (bioinformatics), diff tools, and NLP. The three operations (insert, delete, replace) correspond to three directions in the DP grid (left, up, diagonal).

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
Empty word1	`"", "abc"`	Insert all 3 chars. dp[0][3]=3.
Both empty	`"", ""`	dp[0][0]=0. No operations.
Identical	`"abc", "abc"`	All diagonal matches. dp[3][3]=0.
Completely different	`"abc", "xyz"`	Replace all 3. dp[3][3]=3.
One char difference	`"abc", "adc"`	One replace. dp[3][3]=1.

⚠ Common Mistake: Forgetting to add 1 for the cost of the current operation. The three neighbors give the cost of making the remaining substrings match, but if characters don't match, the current operation itself costs 1. dp[i][j] = 1 + min(...) — not just min(...).

← Back to DP — 2D problems

LearningTree

LC 72 · Edit Distance — Solution & Explanation | DSA Guide