How a Spell-Checker Measures a Word’s Difference
A spell-checker can compare a misspelling with possible corrections by building a small grid. Put the letters of one word across the top and the letters of the other down the side. Each cell records the cheapest edit cost for matching the two prefixes—the portions of the words considered so far.
The first row and column are easy: turning an empty word into a prefix takes one insertion per letter, while removing a prefix takes one deletion per letter. For each remaining cell, the algorithm considers three routes: delete a letter, insert one, or match the current letters—or substitute one for the other if they differ. It keeps the lowest-cost route. The final cell gives the minimum number of edits for the complete words.
Why the Grid Matters
This method, called dynamic programming, avoids trying every possible sequence of edits. Many routes overlap: if two candidate paths both compare the same prefixes, the grid stores that result and reuses it. For words of lengths m and n, the basic method fills roughly m × n cells, making it practical to compare a typed word against many dictionary entries.
For example, changing speling to spelling requires inserting one letter, so their distance is 1. A checker can use that score to rank spelling candidates, often favoring words that need fewer edits.
A Useful Score, Not a Complete Judge
The score treats each permitted edit equally. It does not know that one typo is more likely than another, or that a particular correction makes sense in a sentence. Spell-checkers can combine edit distance with clues such as word frequency or surrounding words. And in the basic version, swapping two neighboring letters counts as two edits, not one. The distance narrows the candidates; other evidence helps choose among them.
