Dynamic Programming — Edit Distance

↗ LeetCode: Edit Distance · Hard · pattern chapter →

Asked atMetaAmazonGoogleMicrosoftUber

Given two strings word1 and word2, return the minimum number of edits (insert, delete, replace) to convert word1 → word2.

Example 1 — word1="horse", word2="ros" → 3Example 2 — word1="intention", word2="execution" → 5

Constraints — 0 ≤ m, n ≤ 500. Brute recursion is O(3^max(m,n)) — at m=n=500 that's ~7·10²³⁸ (dead universes). 2D DP is O(m·n) = 2.5·10⁶ ops = <30 ms; compressed to O(min(m,n)) space.

Progressive Hints

Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.

---

⏱️Interview timer00:00

Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.

Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.

Approach 1 — Brute recursion → Approach 2 — Memoized

Same skeleton as Coin Change / House Robber. At (i, j): if chars match, f(i-1, j-1); else 1 + min(insert, delete, replace). Brute is exponential; memoization brings it to O(m·n).

Approach 3 — Bottom-up DP

java

int minDistance(String a, String b) {
    int m = a.length(), n = b.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++) {
            if (a.charAt(i - 1) == b.charAt(j - 1))
                dp[i][j] = dp[i - 1][j - 1];
            else
                dp[i][j] = 1 + Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1]));
        }
    return dp[m][n];
}

Execution Trace

Edit Distance — word1="horse", word2="ros"

Step 1 / 41 + min(1,1,0) = 1

Complexity — Time O(m·n); Space O(m·n) (reducible to O(min(m,n)) with rolling row).

Try it yourself

Complexity summary

Approach	Time	Space
Brute recursion	O(3^(m+n))	O(m+n)
Memoized	O(m·n)	O(m·n)
Tabulated	O(m·n)	O(m·n)
Rolling row	O(m·n)	O(min(m,n))

When to use which

Standard edit distance → 2D DP.
Only insertions allowed → LCS variant.
Return the operations → track parent choices during DP.

✨AI Study CompanionBeta

Longest Common Subsequence — same shape, different recurrence
Distinct Subsequences — count matches instead
Regular Expression Matching — same 2D table skeleton

Was this page helpful?

📚 Related problems

Dynamic Programming — Edit Distance ​

Approach 1 — Brute recursion → Approach 2 — Memoized ​

Approach 3 — Bottom-up DP ​

Try it yourself ​

Complexity summary ​

When to use which ​

Related problems ​