Edit Distance

Edit distance measures the fewest single-character insertions, deletions, and replacements needed to turn one string into another. The Levenshtein dynamic program solves it by comparing every pair of prefixes, recording the cheapest cost in a table, then tracing the winning predecessors to recover an actual edit script.

A spelling checker can rank nearby words with this score. Fuzzy search, OCR cleanup, and record deduplication use the same shape, usually with costs tuned to the domain instead of the unit costs used here.

Every interior cell asks one blunt question: who pays for the trailing characters? Delete makes the last source character pay, insert makes the last target character pay, and replace charges the pair together. A match is the pleasant exception: both trailing characters disappear from the subproblem for free.

How edit distance works

Let dp[i][j] be the minimum cost of turning source[:i] into target[:j]. The extra row and column represent empty prefixes. Converting i source characters to an empty target requires i deletions, so dp[i][0] = i. Converting an empty source to j target characters requires j insertions, so dp[0][j] = j.

For any other cell, compare source[i - 1] with target[j - 1]. If the characters match, keeping that character costs nothing: dp[i][j] = dp[i - 1][j - 1].

If they differ, the final operation must be one of three choices:

• Delete source[i - 1], leaving dp[i - 1][j] + 1.
• Insert target[j - 1], leaving dp[i][j - 1] + 1.
• Replace the source character with the target character, leaving dp[i - 1][j - 1] + 1.

The cell takes the smallest candidate. Each neighbor is already the exact optimum for a strictly smaller prefix pair, not a guess seen so far. If an optimal conversion ends with a deletion, insertion, or replacement, removing that last edit leaves exactly the corresponding neighbor's subproblem. A cheaper way to solve that neighbor would make the whole conversion cheaper too, which contradicts optimality. That is why a local minimum over the three final moves gives the global optimum for this cell.

The lower-right value is the distance, but it does not list the edits. Traceback supplies that list. A matching diagonal emits a zero-cost keep; a mismatching diagonal emits a replacement; an upward move deletes; and a leftward move inserts. Several predecessors can have the same minimum cost. This lesson prefers replace, then insert, then delete so the animation always returns the same optimal script.

Edit distance step by step

The default run turns KITTEN into SITTING.

1. The algorithm fills the left border with 0, 1, 2, ..., 6 and the top border with 0, 1, 2, ..., 7. Those values are complete solutions for prefix pairs in which one side is empty.

2. The first interior cell compares K with S. Delete and insert both cost 2, while replacing K with S costs 1. The cell records 1 from the diagonal replacement.

3. The table continues row by row. When equal characters meet, as the first I does with the first I, the diagonal value is copied for free. At a mismatch, the candidate panel keeps delete, insert, and replace visible together before committing the minimum. A tie changes the recovered script, not the distance; the lesson picks one predecessor only so replay stays repeatable.

4. After all 42 interior cells are filled, the lower-right cell contains 3. The minimum cost is now known, but the operation ribbon is still empty.

5. Traceback begins at (6, 7). The target has one trailing G, so the path moves left and records insert G. It then keeps N, replaces E with I, keeps the two T characters and I, and replaces K with S.

6. Because traceback runs backward, it fills fixed script slots from right to left. Once complete, the forward order is replace K→S, keep I, keep T, keep T, replace E→I, keep N, insert G. Exactly three chips have cost 1, matching dp[6][7] = 3.

7. The replay applies that script from left to right. It consumes every source character, writes SITTING into the target slots, and confirms that the recorded minimum is achievable.

Why position-by-position comparison fails

The shift-trap preset explains why comparing characters only at equal positions is not enough. ABCDEF and BCDEFG disagree at all six shared positions, yet deleting the leading A and inserting the trailing G costs only 2. One edit can realign an entire suffix.

Time and space complexity

Here m and n are the source and target lengths. The O(m × n) table is usually the first practical limit.

If you need only a score or a yes/no threshold, keep two rows, or one carefully updated row, for O(min(m, n)) space. If a user needs the actual corrections or diff, retain the full table or equivalent predecessor data. When you only accept matches within a small distance k, a banded implementation can avoid computing cells too far from the diagonal.

Edge cases

• Two empty strings have distance 0.
• An empty source needs one insertion per target character. The empty-source preset turns "" into CAT with three insertions.
• An empty target needs one deletion per source character.
• Identical strings follow zero-cost diagonals and have distance 0.
• Repeated characters and tied candidates can produce several different optimal scripts with the same distance.
• Standard Levenshtein distance does not treat transposition as one edit. Turning CA into AC costs 2 under this model.
• The animation accepts up to eight uppercase letters per string to keep the grid readable. That is a presentation limit, not an algorithmic one.

Common mistakes

• Initializing the first row and column to zero. Their values are insertion and deletion counts, not empty placeholders.
• Adding 1 when characters match. Keeping equal trailing characters copies the diagonal cost unchanged.
• Swapping insert and delete during traceback. Moving left inserts a target character; moving up deletes a source character.
• Choosing the cheapest immediate-looking character edit without considering prefix states. Greedy position matching misses useful realignment.
• Computing Hamming distance instead. Hamming distance compares equal-length strings position by position and cannot model insertions or deletions.
• Stopping after reading the lower-right value when an edit script is required. The number proves the optimum cost; traceback supplies a witness.