Levenshtein Distance
Compute the Levenshtein distance between two strings.
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.
Level up your interview prep. Join Educative to access 70+ handson prep courses.