The core measure
Edit distance counts the fewest single character operations needed to transform one string into another. The classic Levenshtein form allows three operations: insert, delete, and substitute.
The dynamic programming table
We fill a grid where each cell holds the distance between a prefix of one string and a prefix of the other.
- If the current characters match, copy the diagonal value.
- Otherwise take the smallest of the three neighboring cells and add one.
The bottom right cell holds the full answer.
Common variants
The same framework bends to many definitions:
- Longest common subsequence distance forbids substitution, allowing only insert and delete.
- Damerau edit distance adds a transposition of two adjacent characters.
- Weighted edit distance charges different costs per operation, useful for spell checking and biology.
Saving space
You never need the whole grid at once. Because each cell depends only on the current and previous rows, you can keep just two rows and reduce memory while still reporting the final distance.
Key idea
Edit distance fills a prefix grid choosing the cheapest of insert delete and substitute, and variants like transposition or weighted costs reuse the same table with small rule tweaks.