Problem 93. Calculate the Levenshtein distance between two strings

Created by Cody Team
Appears in Operations

Difficulty:Rate

Solve Later
Add To GroupÃ‚

This problem description is lifted from http://en.wikipedia.org/wiki/Levenshtein_distance.
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.

Solve

Solution Stats

2580 Solutions
1463 Solvers

Last Solution submitted on Apr 25, 2025

Last 200 Solutions

Problem Comments

3 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 comments

ANNOUNCEMENT

Registration Now Open for MathWorks AUTOMOTIVE CONFERENCE 2025

Hello Community, We're excited to announce that registration is now open for the...

Group

Operations

32 Problems
14 Finishers

Problem Recent Solvers1463

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!