Start — autocorrect knows "how far apart" two words are. You type kitten but meant sitting. How does your phone decide they are close? It counts the fewest single-letter fixes that turn one word into the other: kitten → sitten (change k to s) → sittin (change e to i) → sitting (add a g). Three fixes. That count is the edit distance.
Build — three moves, each costing 1. You may insert a letter, delete a letter, or substitute one letter for another. Matching letters are free. To compare the first $i$ letters of word $X$ with the first $j$ letters of word $Y$, store the cheapest cost in a grid cell $dp[i][j]$. The easy edges come first: turning an $i$-letter word into nothing costs $i$ deletions, so $dp[i][0]=i$; building a $j$-letter word from nothing costs $j$ insertions, so $dp[0][j]=j$.
Deepen — one rule fills every inner cell. Each cell looks at its three neighbours. If the current letters match, $X_i=Y_j$, copy the diagonal for free: $dp[i][j]=dp[i-1][j-1]$. Otherwise pay 1 and take the cheapest repair, $dp[i][j]=1+\min\!\big(dp[i-1][j],\,dp[i][j-1],\,dp[i-1][j-1]\big)$ — delete, insert, or substitute. Filling an $m\times n$ grid row by row is $O(mn)$ time, and since each row needs only the one above it, $O(\min(m,n))$ space is enough. Tracing the choices backward from $dp[m][n]$ recovers the actual edits.
Try this in the sim above. The animation steps a generic compare-and-swap engine, so use it to feel the cost of pairwise comparison. (1) Drag the n slider from 4 to 16 and watch the Step counter climb far faster than $n$ — that quadratic growth is the same $O(mn)$ that fills the edit-distance grid. (2) Set speed to 0.25x and single-step with ▶│ to watch each comparison highlight a pseudocode line. (3) Press ◀◀ then ▶▶ to jump between the empty start and the finished state, the two corners a real $dp$ table reads between.
§3 — Complexity Analysis & Derivation
Symbol
Meaning
n
Input size
T(n)
Time complexity
W(n)
Worst case
A(n)
Average case
Step 1 -- Three Operations. Levenshtein distance: minimum number of single-character edits to transform X into Y. Operations: Insert (add a character), Delete (remove a character), Substitute (replace one character). Each costs 1.
Step 2 -- Recurrence. dp[i][j] = edit distance between X[1..i] and Y[1..j]. If X[i]==Y[j]: free match, dp[i][j]=dp[i-1][j-1]. Else: min of delete (dp[i-1][j]+1), insert (dp[i][j-1]+1), substitute (dp[i-1][j-1]+1).
Step 3 -- Time O(mn) Space O(mn). Two nested loops: O(mn). Space: O(mn) for full table, O(min(m,n)) for 1D optimization (only previous row needed).
Step 4 -- Backtracking. Start at dp[m][n]. If X[i]==Y[j]: match, move diagonally (no cost). Else: move to minimum of the three neighbors -- diagonal=substitute, up=delete, left=insert.
Step 5 -- Damerau-Levenshtein. Adds transposition (swap adjacent characters) as a 4th operation. More accurate for typos. dp[i][j] also considers dp[i-2][j-2]+1 if X[i]==Y[j-1] and X[i-1]==Y[j].
Step 6 -- Applications. Spell checking (find nearest dictionary word). DNA sequence alignment. OCR error correction. Natural language processing (fuzzy string matching). Record deduplication. Git blame / version control diff.
§4 — Frequently Asked Questions
What are the three edit operations? concept+
Delete: remove X[i] (go from dp[i-1][j] + 1). Insert: add Y[j] into X (go from dp[i][j-1] + 1). Substitute: replace X[i] with Y[j] (go from dp[i-1][j-1] + 1). If X[i]==Y[j], no operation needed -- free match from dp[i-1][j-1].
What do the base cases dp[i][0]=i mean? concept+
dp[i][0] = cost to transform X[1..i] into empty string = delete all i characters = i. dp[0][j] = cost to transform empty string into Y[1..j] = insert all j characters = j.
Where is edit distance used in practice? applied+
Spell checkers (Levenshtein distance <= 2 for suggestions). Database fuzzy matching (find records with typos). DNA alignment (mutations = substitutions, insertions, deletions). Plagiarism detection. Search engine query correction (Did you mean?).
What is the relationship between edit distance and LCS? complex+
For insert/delete only (no substitute): Edit Distance = m + n - 2*LCS(X,Y). With substitution: edit distance <= LCS-based. Substitution is more powerful (one op vs two insert+delete). LCS measures similarity; edit distance measures difference.
How is edit distance computed efficiently for spell checking? nonobv+
For spell checking: compute edit distance from query to every dictionary word. Optimization: if edit distance exceeds threshold d, prune early. BK-trees (Burkhard-Keller trees) organize dictionary by edit distance -- O(|dict|^0.4) query for small d. For d<=2, most words are found instantly.
What is Wagner-Fischer algorithm? deep+
The standard DP for edit distance is the Wagner-Fischer algorithm (1974). Space-optimized version uses only two rows: O(min(m,n)) space. Ukkonen's algorithm (1985): only compute the band of width d (given threshold d) -- O(d*min(m,n)) time. For near-identical strings (small d), much faster.
§5 — Misconceptions & Errors
Conceptual Misconceptions
✗ Edit distance is symmetric (d(X,Y) = d(Y,X)).
✓ True for Levenshtein with equal insert/delete costs. Not true for asymmetric cost models (e.g., delete costs 1, insert costs 2). Standard Levenshtein is symmetric.
✗ Substitution counts as 2 operations (delete + insert).
✓ Levenshtein counts substitution as 1 operation. Longest Common Subsequence-based distance (insert/delete only) counts it as 2.
✗ Edit distance of similar strings is always small.
✓ Even one-character different strings can have edit distance proportional to their length. 'abc' to 'cba' has edit distance 2 (substitute a->c, c->a) but 'abcdef' to 'fedcba' has edit distance 6 (every position must change -- the shared letters appear in reversed order, so none can be matched for free).
Implementation Errors
✗ Forgetting base cases: dp[i][0] and dp[0][j].
✓ dp[i][0]=i (delete i chars), dp[0][j]=j (insert j chars). These are essential -- forgetting gives wrong values in the first row and column, corrupting all later cells.
✗ Using dp[i][j-1]+1 for DELETE and dp[i-1][j]+1 for INSERT.
✓ Standard convention: dp[i-1][j]+1 = delete X[i] (ignore X[i], advance only in X). dp[i][j-1]+1 = insert Y[j] (insert Y[j] into X, advance only in Y). Swapping these is a common error.
✗ Backtracking by following minimum value instead of operation type.
✓ Backtrack must correctly identify WHICH operation gave the minimum -- not just the value. For equal minimums (ties), any choice gives a valid edit sequence (may differ from expected output).