Run it
The full table printed for a small pair so the shape is visible, the two-row version checked against it, and the zeroed-base-case bug producing a confidently wrong answer.
The recurrence
Let dp[i][j] be the distance between the first i characters of word1 and the first j of word2.
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], dp[i][j−1], dp[i−1][j−1])
The three options in the min are the three edits, and knowing which is which is what makes the recurrence memorable:
| Term | Edit | Meaning |
|---|
dp[i-1][j] | Delete | Drop word1[i-1] |
dp[i][j-1] | Insert | Add word2[j-1] |
dp[i-1][j-1] | Substitute | Replace one with the other |
If the characters already match, no edit is needed and the cost carries over diagonally.
Base cases: dp[i][0] = i (delete everything) and dp[0][j] = j (insert everything). Getting those wrong is the most common source of off-by-one errors.
O(nm) time and O(nm) space.
The table, filled in
"horse" to "ros":
| | ∅ | r | o | s |
|---|
| ∅ | 0 | 1 | 2 | 3 |
| h | 1 | 1 | 2 | 3 |
| o | 2 | 2 | 1 | 2 |
| r | 3 | 2 | 2 | 2 |
| s | 4 | 3 | 3 | 2 |
| e | 5 | 4 | 4 | 3 |
The answer is the bottom-right cell: 3.
Reading the table is instructive. The diagonal 1 at (o, o) is where a match let the cost carry over. Filling in a small table by hand during an interview is worth doing — it catches base-case and index errors immediately, and it demonstrates the recurrence rather than asserting it.
What each neighbour means
The three options are not arbitrary; each is one edit:
Diagonal (dp[i-1][j-1]) — substitute one character for the other. Free when they already match.
Up (dp[i-1][j]) — delete a character from the first string.
Left (dp[i][j-1]) — insert a character into the first string.
Being able to say which is which is what separates understanding the recurrence from having memorised it.
The base cases
Row 0 and column 0 are the edges: turning a prefix of length i into the empty string costs i deletions, and building a prefix of length j from nothing costs j insertions. Filling them with zeros instead is the most common mistake, and it produces answers that are too small.
Cutting the space
Each cell depends only on the row above and the cell to its left, so the whole table is never needed at once — two rows suffice, and iterating over the shorter string makes it O(min(m, n)).
The trade is that you can no longer walk the table backwards to recover the actual sequence of edits. If the question asks which edits, keep the full table; if it asks only for the count, the two-row version is strictly better.
Reducing space to O(m)
Each row depends only on the row above it, so the full table is unnecessary:
O(min(n, m)) space if you also swap the arguments so the shorter string drives the row width — worth mentioning as the final refinement.
The three lookups map cleanly: prev[j] is above (delete), curr[j-1] is left (insert), prev[j-1] is diagonal (substitute). Keeping that mapping straight is what makes the compressed version writable without re-deriving it.
Note that this loses the ability to reconstruct the edits, which needs the full table — walk backwards from the bottom-right, choosing whichever predecessor produced the value.
The variants
| Variant | Change |
|---|
| Longest common subsequence | Only insert and delete; no substitution |
| Hamming distance | Substitutions only; strings must be equal length |
| Damerau-Levenshtein | Adds transposition of adjacent characters |
| Weighted edit distance | Different costs per operation |
| One edit away? | Early exit once the distance exceeds 1 |
| Levenshtein with a bound k | Only fill a band of width 2k+1 — O(kn) |
The banded version is the practically important one. If you only care whether the distance is at most k, cells far from the diagonal cannot contribute, so only a band needs filling — O(kn) instead of O(nm). That is what makes fuzzy search over large dictionaries feasible.
One edit away has a neat O(n) solution that avoids DP entirely: if the lengths differ by more than 1 the answer is no; otherwise scan once, and on the first mismatch either skip one character in the longer string or skip both, then require the remainder to match exactly.
Where it is used
- Spell checking and autocorrect. Suggest dictionary words within a small edit distance of the typed word.
- Fuzzy search. Elasticsearch's fuzzy queries are bounded Levenshtein.
diff and version control. Line-level longest common subsequence, which is the same DP family.- Bioinformatics. Needleman-Wunsch is edit distance with substitution costs from a scoring matrix; Smith-Waterman is the local-alignment variant.
- Record linkage and deduplication. Matching names and addresses that differ by typos.
- OCR post-processing, correcting recognition errors against a lexicon.
For large-scale fuzzy matching, a BK-tree or a Levenshtein automaton indexes a dictionary so that all words within distance k are retrieved without computing the distance to every entry — which is what a spell checker actually does.
What it is testing
Do you recognise it as dynamic programming? Overlapping subproblems and optimal substructure, with a two-dimensional state.
Can you define the state precisely? "The distance between the first i and the first j characters" is the sentence that makes the recurrence derivable.
Do you get the base cases right? dp[i][0] = i and dp[0][j] = j, which are the deletions and insertions needed against an empty string.
Do you know which term is which edit? Being able to say "up is delete, left is insert, diagonal is substitute" demonstrates understanding rather than recall.
Do you find the space optimisation? One row instead of the full table, and it follows from noticing the dependency pattern.
Recap in one screen
dp[i][j] is the distance between the first i and first j characters.- Matching characters carry the diagonal value; otherwise take 1 plus the minimum of up (delete), left (insert) and diagonal (substitute).
- Base cases are
dp[i][0] = i and dp[0][j] = j. - O(nm) time; space reduces to one row, at the cost of not being able to reconstruct the edits.
- A banded version gives O(kn) when only distances up to k matter — which is what fuzzy search uses.