Levenshtein distance

Levenshtein distance, also known as edit distance, is a metric that measures the amount of differences between two given sequences. Wikipedia says the Levenshtein distance between two strings is given by the minimum number of operations needed to transform one string into the other, where an operation is an insertion, deletion, or substitution of a single character.

Usage: It is often used in applications that need to determine how similar, or different, two strings are, such as spell checkers.

Examples:
The Levenshtein distance between "kitten" and "sitting" is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits:

1. kitten → sitten (substitution of 's' for 'k')
2. sitten → sittin (substitution of 'i' for 'e')
3. sittin → sitting (insert 'g' at the end).