Edit distance measures how different two strings are by counting the minimum number of single-character edits needed to turn one into the other. The allowed operations are insertion, deletion, and substitution.

For example, KITTEN → SITTING takes 3 edits: substitute K→S, substitute E→I, insert G. This metric powers spell checkers, DNA alignment, and fuzzy search.

How It Works

The table dp[i][j] holds the edit distance between the first i characters of string A and the first j characters of string B:

1. Base cases: dp[i][0] = i (delete all of A) and dp[0][j] = j (insert all of B).
2. Match: if A[i-1] == B[j-1], the cost carries over diagonally: dp[i][j] = dp[i-1][j-1].
3. Mismatch: otherwise take the minimum of three options, each costing 1:

   dp[i][j] = 1 + min(
     dp[i-1][j],     // delete A[i-1]
     dp[i][j-1],     // insert B[j-1]
     dp[i-1][j-1]    // substitute A[i-1] with B[j-1]
   )

4. Reconstruct: walk from the bottom-right corner back to the origin, following the moves that produced each value.

Key Insight

Edit distance is a generalization of LCS. Both build a two-dimensional table over two strings and walk diagonally on matches. But:

• LCS asks “how much can I keep?”
• Edit distance asks “what’s the cheapest sequence of edits?” — mismatch costs become explicit.

When only insertions and deletions are allowed (no substitution), the two are linked by edits = m + n − 2·LCS.

Worked Example

The visualizer runs A = KITTEN and B = SITTING:

The bottom-right cell reads 3 — and the traceback recovers the classic path: K→S (substitute), E→I (substitute), insert G. The middle matching run ITT→ITT costs 0, which is why the distance stays small.

Edge Cases & Pitfalls

• Empty string — KITTEN vs "" is 6 (all deletions); "" vs SITTING is 7 (all insertions).
• Identical strings — distance 0: every cell carries over diagonally.
• Cost asymmetry — substitution vs delete+insert. Some variants give substitution cost 2 to force a real replace; classic Levenshtein uses 1.
• Ties — multiple optimal edit sequences exist; the traceback follows one valid path.
• Space — the full table is O(mn). Only the previous row is needed for the distance itself (O(min(m, n))), but reconstruction needs more.

Applications

• Spell checkers — suggest corrections by minimum distance to dictionary words
• Bioinformatics — DNA and protein sequence alignment (Needleman–Wunsch generalizes this)
• Fuzzy search — approximate string matching and diffing

Practice Trajectory

1. Hand-fill the table for KITTEN/SITTING and confirm the bottom-right value is 3.
2. Trace the backtrack and identify each substitute/insert/delete move.
3. Compare with LCS: why does match stay 0, and mismatch become a choice of 3 edits?
4. Reduce space to O(min(m, n)) for the distance-only version.
5. Verify the m + n − 2·LCS identity by computing LCS of the same pair.