Statement

Given two strings, compute the Levenshtein distance between them.

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

Examples

Let’s see a few examples below:

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

  • If s1=tests_1=test and s2=texts_2=text then LD(s1, s2)=1LD(s_1, \space s_2) = 1, because one substitution of xx for ss is required to transform s1s_1 into s2s_2.

  • If s1=ants_1=ant and s2=aunts_2=aunt then LD(s1, s2)=1LD(s_1, \space s_2) = 1, because one insertion of uu after aa is required to transform s1s_1 into s2s_2.

  • If s1=mins_1 =min and s2=maxs_2=max then LD(s1, s2)=2LD(s_1,\space s_2) = 2, because two substitutions are required to transform s1s_1 into s2s_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 80+ hands-on prep courses.