Levenshtein Distance

Statement

Given two strings, compute the Levenshtein distance between them.

The Levenshtein distance, $LD$, is a measure of the difference between two strings, $s_1$ and $s_2$. It is the minimum number of deletions, insertions, or substitutions required to transform $s_1$ into $s_2$. It is also known as the edit distance.

Examples

Let’s see a few examples below:

• If $s_1= ant$ and $s_2= ant$ then $LD(s_1, \space s_2) = 0$, because no transformations are required as the strings are already identical.

• If $s_1=test$ and $s_2=text$ then $LD(s_1, \space s_2) = 1$, because one substitution of $x$ for $s$ is required to transform $s_1$ into $s_2$.

• If $s_1=ant$ and $s_2=aunt$ then $LD(s_1, \space s_2) = 1$, because one insertion of $u$ after $a$ is required to transform $s_1$ into $s_2$.

• If $s_1 =min$ and $s_2=max$ then $LD(s_1,\space s_2) = 2$, because two substitutions are required to transform $s_1$ into $s_2$.

Note: The greater the Levenshtein distance, the more different the strings are, and vice versa.