Skip to content
Back to Generative AIAll lessons

Generative AI

Levenshtein Edit Distance

O(m · n) time and space, where m and n are the lengths of the two words being compared, which is also the size of the grid.

The idea, in plain English

Think about turning the word 'cat' into 'cot'. You only need to change one letter, so they are '1 edit' apart. Edit distance, also called Levenshtein distance, counts the fewest single-letter edits needed to turn one piece of text into another. An edit can be inserting a letter, deleting a letter, or swapping one letter for another. Two identical words are '0 edits' apart. The more edits it takes, the less alike the words are. This is the trick behind a spell-checker's 'did you mean' suggestions, and other fuzzy text matching, meaning matching that is approximate rather than exact.

How it works

  1. 1Build a grid. Give it one row per letter of the first word, plus an extra row for the empty string. Give it one column per letter of the second word, plus an extra column for the empty string.
  2. 2Fill in the first row and column with 0, 1, 2, 3, and so on. Turning an empty string into a growing prefix costs exactly that many letter insertions.
  3. 3Fill in the rest of the grid cell by cell. If the current letters from both words match, copy the value from the diagonal cell up and to the left, since no edit is needed there. If they do not match, take the smallest value among the cell above, the cell to the left, and the diagonal cell, then add 1 for the edit.
  4. 4The number in the grid's bottom-right corner is the edit distance between the two full words.

When you'd use it

Use this for fuzzy string matching, such as spell-check suggestions, 'did you mean' search corrections, matching slightly misspelled names or addresses, and measuring how close a generated string is to an expected one.

Common beginner mistakes

  • Don't confuse edit distance with how different two words look at a glance. 'Flaw' and 'lawn' share every single letter but are still 2 edits apart, because the letters are in a different order.
  • Remember that a lower edit distance always means the words are more similar, and 0 means identical. It is easy to read this backwards by instinct, as if it were a similarity score where higher is better.
  • Don't use edit distance alone to compare words of very different lengths. A short word will always need at least as many edits as the length difference to reach a much longer word, no matter how related the two actually are.

Try it — edit and run

Click the code to edit · press ⌘/Ctrl+↵ to run

Editable code. Tab and Shift+Tab indent. Press Escape, then Tab, to move focus out of the editor.

Expected output — hit Run to try it
Edit distance between word pairs:
kitten -> sitting: 3
flaw -> lawn: 2
intention -> execution: 5

Fuzzy match for "aple" against dictionary: apple, grape, apply, maple
apple: distance 1
grape: distance 3
apply: distance 2
maple: distance 1
Closest match: apple (distance 1)

Note: 'Apple' and 'maple' are tied at distance 1 from 'aple'. The code keeps the first one it finds with the lowest distance so far. Both languages check the dictionary in the same order, so both always pick 'apple'.

Not sure this is the right topic? See the learning paths → or where this leads →