Levenshtein Distance

Calculates the Levenshtein edit distance of two strings using a basic dynamic programming approach adapted from Needleman and Wunsch. The algorithm’s running time is O(nm), as is its space requirement. The space requirement can be pushed down to O(n) (n being the length of the shorter string) by use of Hirschberg’s algorithm.

http://en.wikipedia.org/wiki/Levenshtein_distance