Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Let dp[i][j] be the minimum edits to turn the first i characters of word1 into the first j characters of word2. If the current characters match, dp[i][j] = dp[i-1][j-1] (free). Otherwise dp[i][j] = 1 + min(dp[i-1][j] delete, dp[i][j-1] insert, dp[i-1][j-1] replace). Base cases: dp[i][0] = i, dp[0][j] = j. Naive recursion is exponential; the DP is O(mn) time and O(mn) space, compressible to O(n).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can define a 2D state over two prefixes, map each of insert/delete/replace to a specific neighbouring cell, and get the base cases (which are NOT zero) right.
Where candidates slip
Adding +1 on a character match, mixing up which neighbour is insert vs delete, or initializing the first row/column to 0 instead of 0..n / 0..m.
How to stand out
Derive the recurrence from the last characters, explain why a match is a free diagonal move, note the insert/delete symmetry, then compress to O(n) space with a saved diagonal.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewMin edits to turn word1 into word2Brute force the recursion on last chars?YesNoExplore the full treeCollapse the tree
How to read it:When the last characters differ, each operation corresponds to one neighbouring cell. Pick the cheapest and add one.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 3
Brute Force — Recursion on the Last Characters
1Hint 1Explore hintHide hint
Look at the LAST character of each string. If they're equal, you pay nothing for them and recurse on the two shorter prefixes.
2Hint 2Explore hintHide hint
If they differ, you must do one of three edits to reconcile them: delete word1's last char, insert word2's last char, or replace. Each costs 1 plus the cost of the resulting subproblem.
3Hint 3Explore hintHide hint
Base cases: if one prefix is empty, the answer is the length of the other (all inserts or all deletes).
A · Core idea
Reason about the last characters of the two prefixes word1[0..i) and word2[0..j). If word1[i-1] == word2[j-1], those characters already align, cost nothing, and the problem reduces to converting word1[0..i-1) into word2[0..j-1). If they differ, we must perform one edit to fix the mismatch, and there are exactly three ways:
The three operations, each a shrinking subproblem. Delete word1[i-1]: pay 1, then solve (i-1, j) — word1 lost a character, word2 unchanged. Insert the needed character at word1's end (matching word2[j-1]): pay 1, then solve (i, j-1) — word2's last character is now accounted for, word1 unchanged. Replace word1[i-1] with word2[j-1]: pay 1, then solve (i-1, j-1) — both shrink. We take the minimum of the three and add the 1 we just spent.
Why the base cases are lengths, not zero. If word1 is exhausted (i == 0) but word2 still has j characters, the only way forward is j insertions, so the cost is j. Symmetrically, if word2 is empty we delete all i remaining characters of word1. These boundary costs are the seeds the whole recurrence builds on — initializing them to 0 silently undercounts everything.
Why the insert/delete symmetry matters. 'Insert into word1' and 'delete from word2' produce the same alignment, so we never need separate cases for editing the other string — the three branches already cover every possibility. That symmetry is why a single 2D table suffices.
Why we don't ship this. On a worst-case mismatch every call fans out into three, and the same (i, j) subproblem is recomputed across countless branches — exponential time. For two length-500 strings this never finishes. The overlap is the signal to memoize.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
word1 = "ab", word2 = "ac"solve(2,2)
'b' vs 'c' differ → 1 + min(solve(1,2), solve(2,1), solve(1,1))
branch on mismatch1C · Code with teaching comments
Reference implementation previewpublic int minDistance(String word1, String word2) { return solve(word1, word2, word1.length(), word2.length()); } private int solve(String w1, String w2, int i, int j) {Explore the full codeHide the full code
D · Why it works and complexityO(3^(m+n)) timeO(m + n) spaceOpen the invariant and proofExplore the proofHide the proof
The whole problem falls out of one question: 'what do I do with the last pair of characters?' A match is a free diagonal step; a mismatch is 1 + the cheapest of three shrinking subproblems. Naming those three subproblems (delete, insert, replace) as specific index moves is the entire algorithm — everything after is just caching.
ComplexityO(3^(m+n)) time, O(m + n) space — On a mismatch each call branches into three, and the combined index can decrease up to m+n times — about 3^(m+n) calls in the worst case. The recursion stack is O(m+n) deep.
E · Edge cases and pitfalls5word1 = "", word2 = "abc" — i == 0 fires immediately → returns j = 3 (three inserts).Explore edge casesHide edge cases
Edge cases handled
word1 = "", word2 = "abc"i == 0 fires immediately → returns j = 3 (three inserts).word1 = word2Every character matches, so every step is a free diagonal move down to (0,0) → returns 0.
Pitfalls
- Adding +1 on a character match — equal characters are free.
- Returning 0 instead of the remaining length in the base cases — undercounts every edit.
- Shipping the plain recursion — it's exponential and TLEs well before 500-length strings.
Approach 2 of 3
Top-Down Memoization
1Hint 1Explore hintHide hint
How many distinct subproblems are there really? Each is fully described by the pair (i, j) of prefix lengths — so at most (m+1)(n+1) of them.
2Hint 2Explore hintHide hint
Add a 2D memo indexed by (i, j). Before doing any work, return the cached value if it's already been computed.
3Hint 3Explore hintHide hint
Same recurrence as the recursion, just store the result before returning. Exponential branching collapses because every (i, j) is expanded only once.
A · Core idea
The recursion is correct but redundant: the same (i, j) prefix pair is reached through many different sequences of edits. Since the answer for (i, j) is fixed, we compute it once and cache it.
Why a 2D cache is exactly the right size. Every subproblem is uniquely identified by how much of each string is left — the pair (i, j). There are only (m+1)(n+1) such pairs, so a 2D array (or map) keyed by (i, j) captures every distinct subproblem with no waste. The first time we solve (i, j) we store it; every later request is an O(1) read.
Why this is the gentlest leap from the recursion. The shape of the code barely changes — add a cache check at the top and a cache write before each return. We still start at (m, n) and recurse down toward the base cases, so we don't have to reason about iteration order; the recursion discovers a valid order for us. A sentinel like -1 marks 'not computed', safe because a real edit count is never negative.
Why the cache check must be first. If the guard that returns the cached value isn't the very first thing after the base cases, we'd recurse on every call and stay exponential. Memoization only helps if it short-circuits before the three recursive branches fire.
The payoff. Two length-500 strings produce at most ~251,000 subproblems — each solved once — turning an intractable exponential into a fraction of a second. This is the universal first-DP move: take a correct slow recursion with overlapping subproblems, bolt on a cache, and inherit the optimal time complexity.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
word1 = "ab", word2 = "ac"solve(2,2)
miss → 'b'≠'c', needs (1,2),(2,1),(1,1)
memo = {}1C · Code with teaching comments
Reference implementation previewpublic int minDistance(String word1, String word2) { int m = word1.length(), n = word2.length(); Integer[][] memo = new Integer[m + 1][n + 1]; return solve(word1, word2, m, n, memo); }Explore the full codeHide the full code
D · Why it works and complexityO(mn) timeO(mn) spaceOpen the invariant and proofExplore the proofHide the proof
The number of distinct subproblems equals the size of the state space — here (m+1)(n+1) prefix pairs. Once you see that the exponential recursion only ever revisits this polynomial set of states, caching is guaranteed to collapse the time to the state-space size. That counting argument is how you predict a DP's complexity before writing it.
ComplexityO(mn) time, O(mn) space — There are (m+1)(n+1) distinct (i, j) subproblems; each is computed once with O(1) work and cached → O(mn) time. The memo table plus recursion stack is O(mn) space.
E · Edge cases and pitfalls5word1 = "horse", word2 = "ros" — Only (5+1)(3+1) = 24 subproblems are ever solved, each once → returns 3 instantly.Explore edge casesHide edge cases
Edge cases handled
word1 = "horse", word2 = "ros"Only (5+1)(3+1) = 24 subproblems are ever solved, each once → returns 3 instantly.both length 500~251k cached states instead of exponential calls — finishes in well under a second.
Pitfalls
- Using int[][] with a 0 default in Java — 0 is a valid answer, so you'd mistake real zeros for 'uncomputed'; use Integer/null or a -1 sentinel.
- Placing the cache check after the recursive branches — it then never prevents the recomputation.
- Forgetting to store the result before returning — silently stays exponential.
Approach 3 of 3 · Optimal
Bottom-Up Tabulation — 2D Table, Rollable to O(n) (Optimal)
1Hint 1Explore hintHide hint
Build the table from the smallest prefixes up. Initialize row 0 to 0..n (insert j chars) and column 0 to 0..m (delete i chars).
2Hint 2Explore hintHide hint
Fill row by row: if the characters match, copy the diagonal dp[i-1][j-1]; otherwise 1 + min(left, top, diagonal).
3Hint 3Explore hintHide hint
Each row only depends on the previous row, so you can keep a single 1D array — just remember to save the diagonal before overwriting it.
A · Core idea
Flip the direction: instead of recursing down from (m, n), build the table up from the empty-prefix corner. dp[i][j] is the minimum edits between word1[0..i) and word2[0..j).
Initialize the borders, because they're not zero. dp[0][j] = j — turning the empty string into word2[0..j) needs j inserts. dp[i][0] = i — turning word1[0..i) into empty needs i deletes. These two lines seed the entire table; with them filled, every interior cell has all three of its dependencies (top, left, diagonal) already computed when a row-major scan reaches it.
The transition, in table terms. For interior (i, j): if word1[i-1] == word2[j-1], the characters align for free and dp[i][j] = dp[i-1][j-1] (diagonal, no +1). Otherwise dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]), where dp[i-1][j] is delete, dp[i][j-1] is insert, and dp[i-1][j-1] is replace. The answer is dp[m][n].
Why we can collapse to one row. Each cell reads only the previous row (dp[i-1][*]) and the current row to its left (dp[i][j-1]). So a single 1D array of length n+1 suffices: process it left to right, and it morphs from holding row i-1 to holding row i. The one trap is the diagonal dp[i-1][j-1] — it lives at index j-1, which we overwrite the moment we compute the cell to the left. The fix is the same saved-diagonal trick used in many one-row-back DPs: stash the old dp[j] in a temp before overwriting (it becomes the next column's diagonal), and seed each row with prev = dp[0] set to i (the column-0 base case).
Why bottom-up is the interview-grade answer. It removes recursion entirely — no stack-overflow risk on 500-length inputs — runs in cache-friendly linear passes, and the O(n)-space version shows you understand exactly which history the recurrence needs. That progression (recursion → memo → table → rolled row) is precisely the narrative interviewers reward.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
word1 = "horse", word2 = "ros"Interactive diagram
How one cell reads its three neighbours
bordersMatch copies the diagonal for free; mismatch takes 1 + min of all three. In the rolled version, dp[j] is the top, dp[j-1] the left, and prev the diagonal.
3C · Code with teaching comments
D · Why it works and complexityO(mn) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The borders carry the whole base-case logic: row 0 = 'insert everything', column 0 = 'delete everything'. Get those right and the interior recurrence is mechanical. And because each cell looks back exactly one row, the table compresses to a single row plus one saved-diagonal scalar — the constant-space signature shared by Edit Distance, LCS, and Minimum Path Sum.
ComplexityO(mn) time, O(n) space — Filling an (m+1)×(n+1) table with O(1) work per cell is O(mn) time. Keeping only the previous row (one 1D array of length n+1 plus a scalar) drops space from O(mn) to O(n).
E · Edge cases and pitfalls5word1 = "", word2 = "abc" — m = 0, the row loop never runs, dp stays [0,1,2,3] → returns dp[3] = 3.Explore edge casesHide edge cases
Edge cases handled
word1 = "", word2 = "abc"m = 0, the row loop never runs, dp stays [0,1,2,3] → returns dp[3] = 3.word1 = "abc", word2 = ""n = 0, dp = [0], each row sets dp[0] = i, final dp[0] = 3 → returns 3 deletes.
Pitfalls
- Initializing row 0 / column 0 to all zeros — loses the insert-all / delete-all base costs.
- Forgetting to save prev (the diagonal) before overwriting dp[j] in the rolled version — the match branch then copies a corrupted value.
- Swapping which neighbour is delete vs insert — harmless to the count by symmetry, but it confuses the reasoning and breaks edit-script reconstruction.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int minDistance(String word1, String word2) { int m = word1.length(), n = word2.length(); int[] dp = new int[n + 1]; for (int j = 0; j <= n; j++) { dp[j] = j;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Charging for a match
When word1[i-1] == word2[j-1] the characters already align, so the cost is exactly dp[i-1][j-1] with NO +1. Adding one inflates the distance for every shared character.
Explore the code comparisonHide the code comparison
Charging for a match
When word1[i-1] == word2[j-1] the characters already align, so the cost is exactly dp[i-1][j-1] with NO +1. Adding one inflates the distance for every shared character.
Don't write this
if (w1.charAt(i - 1) == w2.charAt(j - 1)) {
dp[i][j] = 1 + dp[i - 1][j - 1];
}Write this instead
if (w1.charAt(i - 1) == w2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1];
}2Zeroed base row/column
dp[0][j] must be j (insert j chars) and dp[i][0] must be i (delete i chars). Leaving them 0 tells the DP an empty string is free to grow, undercounting every answer.
Explore the code comparisonHide the code comparison
Zeroed base row/column
dp[0][j] must be j (insert j chars) and dp[i][0] must be i (delete i chars). Leaving them 0 tells the DP an empty string is free to grow, undercounting every answer.
Don't write this
dp = [[0] * (n + 1) for _ in range(m + 1)]
# borders left at 0Write this instead
dp = [[0] * (n + 1) for _ in range(m + 1)]
for j in range(n + 1):
dp[0][j] = j
for i in range(m + 1):
dp[i][0] = i3Lost diagonal in the rolled row
In the O(n) version, dp[j-1] gets overwritten with the current row before the next cell reads it as a diagonal. Failing to stash the previous value in temp/prev corrupts the match branch.
Explore the code comparisonHide the code comparison
Lost diagonal in the rolled row
In the O(n) version, dp[j-1] gets overwritten with the current row before the next cell reads it as a diagonal. Failing to stash the previous value in temp/prev corrupts the match branch.
Don't write this
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[j] = dp[j-1] # this is the LEFT, not the diagonal!
else:
dp[j] = 1 + min(dp[j], dp[j-1], dp[j-1])Write this instead
for j in range(1, n + 1):
temp = dp[j]
if word1[i-1] == word2[j-1]:
dp[j] = prev
else:
dp[j] = 1 + min(dp[j], dp[j-1], prev)
prev = tempRevise
Carry the pattern into the interview
Pattern to remember
2D string DP — Levenshtein distance
Code pattern to memorize
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], # delete
dp[i][j-1], # insert
dp[i-1][j-1]) # replace
base: dp[i][0] = i, dp[0][j] = jRules to remember
- 1dp[i][j] = min edits to convert word1[0..i) into word2[0..j) — both indices are PREFIX LENGTHS, not positions.
- 2On a character match, the cost is
dp[i-1][j-1]with no +1 — equal characters are free, the single most common slip. - 3On a mismatch, the three options map exactly:
dp[i-1][j]= delete,dp[i][j-1]= insert,dp[i-1][j-1]= replace — all+1. - 4Base cases are not zero:
dp[i][0] = i(delete all of word1) anddp[0][j] = j(insert all of word2). - 5The recurrence is symmetric: insert into word1 ≡ delete from word2, so you never need a separate 'insert vs delete from the other string' case.
Use this pattern when
- Transforming one sequence into another with insert / delete / replace operations
- Measuring similarity or alignment between two strings
- Two indices that each march independently through two sequences
- Diff tools, spell-checkers, DNA alignment, fuzzy matching
Choose another pattern when
- Only deletions allowed (no insert/replace) → Longest Common Subsequence in disguise
- Operations have non-uniform costs → weighted DP, but same table shape
- You need the actual edit script, not just the count → backtrack through the dp table
- Strings are huge and only similarity bucket matters → approximate / hashing methods
Interview takeaway
Edit Distance is the archetype of two-pointer string DP: a 2D table indexed by prefix lengths, with a match branch (diagonal, free) and a mismatch branch (1 + min of three neighbours). Master this and Longest Common Subsequence, Delete Operation for Two Strings, and One Edit Distance all become the same table with tweaked transitions.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical 2D string DP (Levenshtein). Recognize it whenever two sequences are aligned with insert/delete/replace and each state is a pair of prefix lengths. The same table powers Longest Common Subsequence, Delete Operation for Two Strings, and Minimum ASCII Delete Sum — change only the match/mismatch transitions.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Longest Common SubsequenceSame 2D prefix table; on a match take diagonal + 1, on a mismatch take max(top, left) — no replace branch.
- Delete Operation for Two StringsComing soonOnly deletes allowed — answer is m + n − 2·LCS, or the same table with just delete/insert branches.
- One Edit DistanceComing soonAsk only whether the distance is exactly 1 — solvable in O(m+n) with a single careful two-pointer scan.
- Minimum ASCII Delete Sum for Two StringsComing soonWeighted variant: instead of counting deletes, minimize the summed ASCII values of deleted characters.