Levenshtein Distance

Levenshtein Distance or edit distance between two strings is the number of single character edits to be made to convert one string to another. The edit can be an insertion, deletion or substitution.

Eg: Levenshtein distance between 'Choose' and 'Shoes' is 3.

1. Substitute 'C' with 'S'
2. Substitute 2nd 'o' with 'e'
3. Delete 's'

C h o o s e
S h o o s e
S h o e s e
S h o e s _

The Damerau–Levenshtein Distance is also an edit distance between two strings but it includes one more edit operation viz transposition.

Eg: Damerau–Levenshtein distance 'Reign' and 'Field' is 4

1. Substitute 'R' with 'F'
2. Transpose 'i' and 'e'
3. Substitute 'g' with 'l'
4. Substitute 'n' with 'd'

R e i g n
F e i g n
F i e g n
F i e l n
F i e l d

Levenshtein distance between 'Reign' and 'Field' is 5.