The moment edit distance clicks is when you stop counting character edits and start editing prefixes. You’re handed two strings and asked for the fewest single-character insertions, deletions, or replacements that turn the first into the second. On LeetCode it’s problem 72, tagged Hard, with both strings capped at 500 characters. That cap tells you what the interviewer wants: a 500 by 500 grid is a quarter-million cells, nothing for a modern CPU, so an O(mn) dynamic programming solution is the target and anything fancier is a sign you’re overthinking it.
The quantity has a name outside interview rooms. It’s the Levenshtein distance, and it sits underneath spell checkers, fuzzy search, git diff, and DNA sequence alignment. Naming that in the room is worth a sentence, because it signals you’ve seen the problem do real work rather than only grinding it on a practice site.
Start from the ends of both strings
Get the recursion right before you draw any table, because the table is only the recursion with the repeated work stripped out. Look at the last character of each string. If word1[i-1] and word2[j-1] are the same, they cost nothing and the problem shrinks to the two prefixes without them. If they differ, you’re spending one operation, and there are three ways to spend it.
Replace word1‘s last character with word2‘s, which aligns both endings and drops you to the smaller problem on both prefixes. Delete word1‘s last character, which shrinks only the first string. Or insert word2‘s last character onto word1, which matches and consumes word2‘s last character and shrinks only the second string. Take the cheapest of those three, add one for the operation, and recurse.
Written literally, that recursion is exponential, because the same prefix pair gets recomputed through many different edit orders. Comparing “horse” with “ros” branches into a tree that revisits the (“hor”, “ro”) subproblem more than once. The fix is the standard one: there are only (m+1)(n+1) distinct prefix pairs, so memoize on (i, j) and each subproblem gets solved a single time.
The table is a grid of prefix answers
Turn that memo into a bottom-up table and the reasoning gets cleaner. Let dp[i][j] be the edit distance between the first i characters of word1 and the first j characters of word2. The value you return is dp[m][n], the bottom-right corner.
The first row and first column are free. Turning an empty string into the first j characters of word2 takes j insertions, so dp[0][j] = j. Turning the first i characters of word1 into an empty string takes i deletions, so dp[i][0] = i. Every other cell reads three neighbors you’ve already computed: the one up and to the left, the one directly above, and the one directly to the left.
| Operation | Cell it reads | Cost added | What it means |
|---|---|---|---|
| Match (word1[i-1] equals word2[j-1]) | dp[i-1][j-1] | 0 | Last characters already agree, shrink both prefixes |
| Replace | dp[i-1][j-1] | 1 | Change word1[i-1] into word2[j-1] |
| Delete | dp[i-1][j] | 1 | Remove word1[i-1], keep all of word2’s prefix |
| Insert | dp[i][j-1] | 1 | Add word2[j-1] onto word1 |
| Empty word1 prefix (i = 0) | n/a | j | j insertions build word2’s first j characters |
| Empty word2 prefix (j = 0) | n/a | i | i deletions empty word1’s first i characters |
When the last characters differ, dp[i][j] is one plus the smallest of the replace, delete, and insert cells. When they match, it copies the up-left diagonal with nothing added. Here is that logic in Python, filling the border first and then sweeping the interior row by row.
def min_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i # delete i chars to reach ""
for j in range(n + 1):
dp[0][j] = j # insert j chars from ""
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(
dp[i - 1][j - 1], # replace
dp[i - 1][j], # delete
dp[i][j - 1], # insert
)
return dp[m][n]
Trace “horse” to “ros” through the table and you land on 3: replace the ‘h’ with ‘r’ to get “rorse”, delete the extra ‘r’ to get “rose”, delete the ‘e’ to get “ros”. The grid finds that without ever naming the operations, which is the whole appeal. It weighs every edit order at once and keeps only the cheapest running total in each cell, so you never sit there reasoning about which sequence of edits happens to be best.
Cutting the space down to one row
The follow-up you should expect the second you finish the O(mn)-space version is whether you can do better on memory. You can. Each cell depends only on the current row and the row directly above, so two rows of length n+1 are enough. Keep a prev row, build a curr row, then swap them.
def min_distance(word1, word2):
m, n = len(word1), len(word2)
prev = list(range(n + 1)) # distance from "" to word2[:j]
for i in range(1, m + 1):
curr = [i] + [0] * n
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
curr[j] = prev[j - 1]
else:
curr[j] = 1 + min(prev[j - 1], prev[j], curr[j - 1])
prev = curr
return prev[n]
That’s O(n) space with the same O(mn) time. If the interviewer keeps pushing, you can collapse to a single row plus one saved value for the up-left diagonal, since that diagonal is the only neighbor you destroy when you overwrite the row in place. I’d stop at two rows unless asked, because the single-row version reads worse and saves very little.
The follow-ups interviewers actually reach for
Reconstructing the edits is the most common extension. The distance number is rarely the real goal; a diff viewer needs the actual sequence of operations. Keep the full table (the O(mn)-space one, not the two-row version) and walk backward from dp[m][n], at each step moving to whichever neighbor your value came from. A diagonal move on matching characters is a keep, a diagonal on a mismatch is a replace, a vertical move is a delete, and a horizontal move is an insert. The space optimization and the traceback pull against each other, and pointing that out before you’re asked reads well.
Weighted edit distance comes next. Real spell checkers don’t treat every edit as cost one. Substituting ‘m’ for ‘n’ should be cheaper than substituting ‘m’ for ‘q’, because the first is a far more likely typo. The recurrence barely moves: replace the hard-coded 1 with a cost function of the two characters. Damerau-Levenshtein goes one step further with a fourth operation, swapping two adjacent characters, so “teh” for “the” counts as one edit instead of two.
The one that catches people is the easy-sounding cousin, LeetCode 161, “one edit distance”: is the distance exactly one? Building the full table and checking for a 1 works, but it’s O(mn) for a question that’s O(n). Scan the strings once, and at the first mismatch decide from the length difference whether a single insert, delete, or replace could still make them equal. Reaching for the heavy table here is a small tell that you’re pattern-matching instead of thinking about the problem in front of you.
What the grader is watching for
The recurrence is common enough that landing the right number isn’t the whole test. Interviewers watch whether you frame the problem around prefixes instead of poking at the middle of the strings, whether your base cases are the empty-string row and column rather than an afterthought, and whether you can say what each of the three neighbors means. Mixing up which neighbor is the insert and which is the delete is the classic bug, and it yields a table that’s wrong by a little in a way that’s miserable to debug against the clock. State what each direction does before you write the loop and you tend to catch it early.
If you’ve done longest common subsequence, most of this is already in your hands. Same grid, same prefix framing, and with only insertions and deletions allowed the edit distance equals m + n minus twice the LCS length. Add replacement and the two measures diverge, but the habit of filling a two-string table transfers straight over, which is why this problem is worth drilling until the border cases come out without a second thought.
Drill the patterns next:
