Live model · Autocorrect
How Autocorrect Actually Works
At its core, autocorrect compares the word you typed with every word in its dictionary. For each one, it counts the fewest letters you'd have to insert, delete or replace to get there. That count is the edit distance. The closest word wins, and a tie goes to the more common word.
Edit distance, one cell at a time
- CH1 ↖ keep/replace
- CH2 ↑ delete
- CH3 ← insert
How to read the grid
Each cell holds the edit distance between the first letters of one word and the first letters of the other. Where the two letters match, the cell copies its diagonal neighbour. Otherwise it takes 1 plus the cheapest of three neighbours: diagonal to replace, up to delete, left to insert. The bottom-right cell is the answer, and the highlighted path traces the edits back.
Type a word
The model scores your word against the 3,000 most common English words, most common first, and keeps the five closest. Pick a suggestion to see its grid. Try a real slip, then one that fools it: swapped letters cost two edits here, so “recieve” lands on “believe”.
All 3,000 scored. "definitely" is the closest, 1 edit away.
“definately” → “definitely”
| rows a, columns b | d | e | f | i | n | i | t | e | l | y | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | |
| d | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| e | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| f | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| i | 4 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| n | 5 | 4 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| a | 6 | 5 | 4 | 3 | 2 | 1 | 1 | 2 | 3 | 4 | 5 |
| t | 7 | 6 | 5 | 4 | 3 | 2 | 2 | 1 | 2 | 3 | 4 |
| e | 8 | 7 | 6 | 5 | 4 | 3 | 3 | 2 | 1 | 2 | 3 |
| l | 9 | 8 | 7 | 6 | 5 | 4 | 4 | 3 | 2 | 1 | 2 |
| y | 10 | 9 | 8 | 7 | 6 | 5 | 5 | 4 | 3 | 2 | 1 |
- CH1 ↖ keep/replace
- CH2 ↑ delete
- CH3 ← insert
Return dp[10][10] = 1: replace a with i.
Questions
- Is this what my phone does?
- It's the core. Phone keyboards also weigh which keys sit next to the one you hit and which word fits after the ones before it, and they learn the words you use. The step they all share is this one: score the dictionary by how close each word is to what you typed.
- Why doesn't “teh” become “the”?
- Swapping two letters counts as two edits here, one replacement for each letter. “ten” is one edit from “teh”, so it wins. Many spell checkers use Damerau–Levenshtein distance instead, which counts a swap of neighbouring letters as one edit and fixes this.
- Why does “helo” become “help” and not “hello”?
- Both are one edit away, and so are “held”, “hell” and “hero”. A tie goes to the most common word, and “help” is far more common than “hello”. Real spell checkers also model which slips people make most, like typing one l where there should be two.
- What is edit distance?
- The fewest single-letter inserts, deletes and replacements that turn one word into another. It's also called Levenshtein distance, after Vladimir Levenshtein, who described it in 1965. Filling the grid takes one step per cell, so two 10-letter words take 100 steps.
Drill the mechanism
The grid is dynamic programming: each cell is built from answers already in the table. Word Break runs the same idea over a string and a dictionary. Coin Change takes 1 plus the cheapest earlier answer, as each edit does, and Climbing Stairs is the smallest table of all.