How far apart are two words? The Levenshtein distance counts the fewest single-character edits — insert, delete, or substitute — to turn one into the other. ‘kitten’ to ‘sitting’ is three. A little dynamic-programming grid finds it exactly, and it’s the engine behind spell-check, DNA alignment, and diff. Slide through word pairs and read the grid.
Levenshtein distance is the minimum number of insertions, deletions, and substitutions to transform string a into string b. A dynamic-programming table d[i][j] = min(d[i−1][j]+1, d[i][j−1]+1, d[i−1][j−1]+[aᵢ≠bⱼ]) fills in O(mn), and the bottom-right cell is the answer. d(a,a)=0 and d(‘kitten’,‘sitting’)=3 (k→s, e→i, +g). A fail-loud self-check throws unless those exact values hold. ◆ real algorithm, node-verified.
The pairs shown are illustrative; the DP recurrence and its distances are exact and optimal. Character-level edit distance is one metric of ‘closeness’ — it says nothing about MEANING, only spelling.