Implementing Levenshtein distance

In information theory (http://en.wikipedia.org/wiki/Information_theory) and computer science (http://en.wikipedia.org/wiki/Computer_science), the Levenshtein distance is a string metric (http://en.wikipedia.org/wiki/String_metric) for measuring the amount of difference between two sequences. The term edit distance (http://en.wikipedia.org/wiki/Edit_distance) is often used to refer specifically to Levenshtein distance.

The Levenshtein distance between two strings (http://en.wikipedia.org/wiki/String_(computer_science)) is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character. It is named after Vladimir Levenshtein (http://en.wikipedia.org/wiki/Vladimir_Levenshtein), who considered this distance in 1965.