The Levenshtein distance is a string metric for measuring the difference between two sequences of characters. It can be used to find quite efficiently the closest word to a short sequence of characters such as a misspelled word. I optimized the algorithm as best I could so that it executes almost instantly, even on large strings of characters. If you want to use this algorithm in one of your projects, simply copy the "Levenshtein distance" sprite. The algorithm's usage is explained in the project. The Levenshtein distance between two words is the minimum number of single-character edits (insertions, deletions or substitutions) required to change one word into the other. It is named after Soviet mathematician Vladimir Levenshtein, who defined the metric in 1965. For example, the Levenshtein distance between "kitten" and "sitting" is 3, since the following 3 edits change one into the other, and there is no way to do it with fewer than 3 edits: 1. kitten → sitten (substitution of "s" for "k") 2. sitten → sittin (substitution of "i" for "e") 3. sittin → sitting (insertion of "g" at the end) Credits: - Wikipedia page on the Levenshtein distance
