Levenshtein Distance
The Levenshtein Distance(a.k.a edit distance) represents the minimum number of edits required to transform one string to another. It measures the similarity of two strings. The smaller the Levenshtein distance, the similar the strings are. Perform dynamic programming to solve the edit distance of substrings and then get the resulting Levenshtein distance of the original two strings at the end.
Table of Contents· Levenshtein Distance
· Approach
· Graphical Explanation
· Code Implementation
∘ Complexity
∘ Golang
∘ Python
Levenshtein Distance
The Levenshtein distance between two strings represents the minimum number of edits required to convert one string to another. It is also called edit distance. The smaller the Levenshtein distance, the similar the strings are.
Three edit operations can be used:
- Insertion
- Deletion
- Replacement
Approach
Maintain a distance matrix to store the Levenshtein distance of substrings and calculate the Levenshtein distance using dynamic programming until we reach the bottom-right element.
string1 → string2case 1: letter in string1 == letter in string2:
distance[r][c] = distance[r-1][c-1]case 2: letter in string1 != letter in string2:
distance[r][c] = 1 + min(distance[r][c-1], # deletion
distance[r-1][c-1], # replacement
distance[r-1][c]) # insertion
Graphical Explanation
string1: horse
string2: iosconvert string1 to string2
- step1: initialize and prepare the distance matrix
- step2: calculate the Levenshtein distance using dynamic programming
Code Implementation
Complexity
Time: O(r*c)
Space: O(r*c)
r: the length of the string2
c: the length of the string1
