Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

Levenshtein Distance

Explore how to calculate the Levenshtein distance, the measure of difference between two strings by counting insertions, deletions, and substitutions. Understand recursive and iterative dynamic programming solutions along with their time and space complexities to improve problem-solving skills for coding interviews.

We'll cover the following...

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= ...