#72 Edit Distance
the problem
In plain words
Return the minimum number of operations (insert a character, delete a character, replace a character) to turn word1 into word2.
in word1 = "horse", word2 = "ros"
out 3
horse → rorse (replace h) → rose (delete r) → ros (delete e).
in word1 = "intention", word2 = "execution"
out 5
- 0 ≤ word1.length, word2.length ≤ 500
- Lowercase English letters
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
pattern2D DP on two strings (LCS / edit distance)
where this runsSpell checkers and "did you mean" search suggest dictionary words with a small edit distance from what you typed.
Look at the last characters. Equal → free, solve the shorter prefixes. Different → 1 + the cheapest of replace (↖), delete (↑), insert (←).
solutions
From brute force to optimal
dist(i, j) tries the three edits when the last chars differ.
- i = 0 → j inserts; j = 0 → i deletes.
- Match → dist(i−1, j−1).
- Else 1 + min of the three.
Up to three branches per call, depth m + n.
Recursion depth.
class Solution { public int minDistance(String word1, String word2) { return dist(word1, word2, word1.length(), word2.length()); } /** Edits to turn the first i chars of a into the first j chars of b. */ private int dist(String a, String b, int i, int j) { if (i == 0) return j; // insert the remaining j chars if (j == 0) return i; // delete the remaining i chars if (a.charAt(i - 1) == b.charAt(j - 1)) return dist(a, b, i - 1, j - 1); int replace = dist(a, b, i - 1, j - 1); int delete = dist(a, b, i - 1, j); int insert = dist(a, b, i, j - 1); return 1 + Math.min(replace, Math.min(delete, insert)); }}Only (m + 1)(n + 1) states.
- memo filled with −1.
- Check, compute, store.
Each state once.
Memo + stack.
class Solution { public int minDistance(String word1, String word2) { int[][] memo = new int[word1.length() + 1][word2.length() + 1]; for (int[] row : memo) Arrays.fill(row, -1); return dist(word1, word2, word1.length(), word2.length(), memo); } private int dist(String a, String b, int i, int j, int[][] memo) { if (i == 0) return j; if (j == 0) return i; if (memo[i][j] != -1) return memo[i][j]; int result; if (a.charAt(i - 1) == b.charAt(j - 1)) result = dist(a, b, i - 1, j - 1, memo); else result = 1 + Math.min(dist(a, b, i - 1, j - 1, memo), Math.min(dist(a, b, i - 1, j, memo), dist(a, b, i, j - 1, memo))); return memo[i][j] = result; }}dp[i][j] = edits to turn the first i chars of word1 into the first j of word2.
- dp[i][0] = i, dp[0][j] = j.
- Same char → dp[i−1][j−1].
- Else 1 + min(dp[i−1][j−1], dp[i−1][j], dp[i][j−1]).
One cell at a time, O(1) each.
The table.
class Solution { public int minDistance(String word1, String word2) { int m = word1.length(), n = word2.length(); int[][] dp = new int[m + 1][n + 1]; for (int i = 0; i <= m; i++) dp[i][0] = i; // delete all i chars for (int j = 0; j <= n; j++) dp[0][j] = j; // insert all j chars 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] = dp[i - 1][j - 1]; // same char: free } else { dp[i][j] = 1 + Math.min(dp[i - 1][j - 1], // replace Math.min(dp[i - 1][j], // delete dp[i][j - 1])); // insert } } } return dp[m][n]; }}Watch the edits
Keep one row; save the old up-left value in diag before overwriting.
- dp = row 0.
- For each row: diag = old dp[0], dp[0] = i.
- For each j: up = dp[j]; compute; diag = up.
Same cells.
One row (swap the words to make it O(min(m, n))).
class Solution { public 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; // row 0: insert j chars for (int i = 1; i <= m; i++) { int diag = dp[0]; // dp[i-1][j-1] for j = 1 dp[0] = i; // column 0: delete i chars for (int j = 1; j <= n; j++) { int up = dp[j]; // dp[i-1][j], about to be overwritten if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[j] = diag; // same char: free else dp[j] = 1 + Math.min(diag, Math.min(up, dp[j - 1])); // replace, delete, insert diag = up; // old dp[j] is the next cell's diagonal } } return dp[n]; }}One row and a saved diagonal
in the room
How to say it in the interview
talk track
- Explain each neighbour in words: ↖ replace the last char, ↑ delete word1's last char, ← insert word2's last char.
- Base cases are the most-forgotten part — say them explicitly.
traps
- Forgetting the base row/column (all zeros gives wrong answers for empty prefixes).
- In the 1-row version, overwriting dp[j] before saving it as the next diagonal.
what they ask next
Follow-ups
One Edit Distance (LC 161) — are they exactly one edit apart?
No DP needed: two pointers, allow one mismatch, O(n).
Only insert and delete allowed (LC 583)?
Answer = m + n − 2·LCS.
before you submit
Edge cases to test
- Either word empty → the other word's length.
- Equal words → 0.
- "intention" → "execution" → 5: letters that already match in the middle are free.
practise next
Similar problems
- #1143Longest Common SubsequenceMediumin Dynamic Programming
- #139Word BreakMediumin Dynamic Programming