Given two strings, compute the Levenshtein distance between them.
The Levenshtein distance, , is a measure of the difference between two strings, and . It is the minimum number of deletions, insertions, or substitutions required to transform into . It is also known as the edit distance.
Let’s see a few examples below:
If and then , because no transformations are required as the strings are already identical.
If and then , because one substitution of for is required to transform into .
If and then , because one insertion of after is required to transform into .
If and then , because two substitutions are required to transform into .
Note: The greater the Levenshtein distance, the more different the strings are, and vice versa.