The edit (Levenshtein) distance counts the fewest single-letter inserts, deletes and replacements that turn one word into another. Each cell of the table builds on three smaller problems: drop A’s last letter, add B’s last letter, or match the last letters up.
- Average time
- O(mn)
- Space
- O(mn)