Problem 93. Calculate the Levenshtein distance between two strings
The Levenshtein distance between two strings is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character.
For example, the Levenshtein distance between "kitten" and "sitting" is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits:
kitten => sitten (substitution of 's' for 'k')
sitten => sittin (substitution of 'e' for 'i')
sittin => sitting (insert 'g' at the end).
So when
s1 = 'kitten'
and
s2 = 'sitting'
then the distance d is equal to 3.
Solution Stats
Problem Comments
-
3 Comments
jj L
on 9 Aug 2018
Good question
Stephan Allgeier
on 10 Jan 2020
I really like this problem. So far, this is the one I had to think about most. Mostly because the straight-forward recursive implementation is simply not feasible for longer inputs.
Roie Knaanie
on 15 Oct 2022
This question is a good example of using a bottom-up dynamic programming algorithm.
Solution Comments
Show commentsProblem Recent Solvers1422
Suggested Problems
-
Given an unsigned integer x, find the largest y by rearranging the bits in x
1816 Solvers
-
448 Solvers
-
We love vectorized solutions. Problem 1 : remove the row average.
818 Solvers
-
Piecewise linear interpolation
545 Solvers
-
785 Solvers
More from this Author96
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!