HomeOur TeamContact Dynamic Programming
Levenshtein Distance Sameer
May 20, 2021
1 min

# .css-10kjd3a{box-sizing:border-box;margin:0;min-width:0;display:block;color:var(--theme-ui-colors-heading,#2d3748);font-weight:900;-webkit-text-decoration:none;text-decoration:none;margin-bottom:1rem;font-size:1.875rem;position:relative;}@media screen and (min-width:640px){.css-10kjd3a{font-size:2.25rem;}}@media screen and (min-width:1024px){.css-10kjd3a{font-size:3rem;}}Levenshtein Distance

Write a function that takes in two strings and returns the minimum number of edit operations that need to be performed on the first string to obtain the second string.

There are three edit operations: insertion of a character, deletion of a character, and substitution of a character for another.

Sample Input

```str1 = "abc"
str2 = "yabd"
```

Sample Output

```2 // insert "y"; substitute "c" for "d"
```

Hint 1 Try building a two-dimensional array of the minimum numbers of edits for pairs of substrings of the input strings. Let the rows of the array represent substrings of the second input string str2. Let the first row represent the empty string. Let each row i thereafter represent the substrings of str2 from 0 to i, with i excluded. Let the columns similarly represent the first input string str1.

Hint 2 Build up the array mentioned in Hint #1 one row at a time. In other words, find the minimum numbers of edits between all the substrings of str1 represented by the columns and the empty string represented by the first row, then between all the substrings of str1 represented by the columns and the first letter of str2 represented by the second row, etc., until you compare both full strings. Find a formula that relates the minimum number of edits at any given point to previous numbers.

Hint 3 At any position (i, j) in the two-dimensional array, if str2[i] is equal to str1[j], then the edit distance at position (i, j) is equal to the one at position (i - 1, j - 1), since adding str2[i] and str1[j] to the substrings represented at position (i - 1, j - 1) does not require any additional edit operation. If str2[i] is not equal to str1[j] however, then the edit distance at position (i, j) is equal to 1 + the minimum of the edit distances at positions (i - 1, j), (i, j - 1), and (i - 1, j - 1). Why is that the case?

Hint 4 Do you really need to store the entire two-dimensional array mentioned in Hint #1? Identify what stored values you actually use throughout the process of building the array and come up with a way of storing only what you need and nothing more.

Optimal Space & Time Complexity O(nm) time | O(min(n, m)) space - where n and m are the lengths of the two input strings

```# O(nm) time | O(nm) space
DEFINE FUNCTION levenshteinDistance(str1, str2):
SET edits TO [[x FOR x IN range(len(str1) + 1)] FOR y IN range(len(str2) + 1)]
FOR i IN range(1, len(str2) + 1):
SET edits[i] TO edits[i - 1] + 1
FOR i IN range(1, len(str2) + 1):
FOR j IN range(1, len(str1) + 1):
IF str2[i - 1] EQUALS str1[j - 1]:
SET edits[i][j] TO edits[i - 1][j - 1]
ELSE:
SET edits[i][j] TO 1 + min(edits[i - 1][j - 1], edits[i - 1][j], edits[i][j - 1])
RETURN edits[-1][-1]
```

### Solution 2

```# O(nm) time | O(min(n, m)) space
DEFINE FUNCTION levenshteinDistance(str1, str2):
SET small TO str1 IF len(str1) < len(str2) else str2
SET big TO str1 IF len(str1) >= len(str2) else str2
SET evenEdits TO [x FOR x IN range(len(small) + 1)]
SET oddEdits TO [None FOR x IN range(len(small) + 1)]
FOR i IN range(1, len(big) + 1):
IF i % 2 EQUALS 1:
SET currentEdits TO oddEdits
SET previousEdits TO evenEdits
ELSE:
SET currentEdits TO evenEdits
SET previousEdits TO oddEdits
SET currentEdits TO i
FOR j IN range(1, len(small) + 1):
IF big[i - 1] EQUALS small[j - 1]:
SET currentEdits[j] TO previousEdits[j - 1]
ELSE:
SET currentEdits[j] TO 1 + min(previousEdits[j - 1], previousEdits[j], currentEdits[j - 1])
RETURN evenEdits[-1] IF len(big) % 2 EQUALS 0 else oddEdits[-1]
```

## Tags

#Difficulty Medium#Algorithm
Previous Article
Line Through Points
Next Article
Largest Range

Heap Sort
January 31, 2022
1 min