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=t$ ...