Levenshtein distance

Levenshtein Distance is a way to measure how different two words or phrases are from each other. It is sometimes called Edit Distance, because it measures how many "edits" (changing, adding or deleting letters) are needed to change one word into the other. For example, if you want to change the word "cat" into the word "dog", you would need three edits: changing the "c" to a "d", adding an "o", and adding a "g", so the Levenshtein Distance between "cat" and "dog" is 3.