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.

Levenshtein distance summary card

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:

1. Insertion
2. Deletion
3. 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 → string2
case 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

approach

Graphical Explanation

LeetCode 72: Edit Distance

string1: horse
string2: ios
convert string1 to string2

• step1: initialize and prepare the distance matrix
• step2: calculate the Levenshtein distance using dynamic programming

process

Code Implementation

Complexity

Time: O(r*c)
Space: O(r*c)
r: the length of the string2
c: the length of the string1

Golang

Python

You can access the source code here.

LeetCode Problem:

• 72: Edit Distance