Levenshtein distance

The Levenshtein distance between two strings is the number of single character deletions, insertions, or substitutions required to transform one string into the other. This is also known as the edit distance.

Analysis of this algorithm can be found at the Mathworks blog and at NIST.