Problem 2309. Calculate the Damerau-Levenshtein distance between two strings.

Problem 2303 reminded me a few older ones dealing with metrics between strings, problems 93, 846 or 848 about Hamming and Levenshtein distances.

Damerau-Levenshtein distance is an extension to Levenshtein distance. It is also defined as minimum number of simple edit operations on string to change it into another, but the list of allowed operations is extended.

As it is written on Wikipedia there are 4 allowed edits: deletion, insertion and substitution of an single character and an transposition of two adjacent characters.

Example. Such defined distance between words gifts and profit is 5:

gifts   => pgifts    (insertion of 'p')
pgifts  => prgifts   (insertion of 'r')
prgifts => proifts   (substitution of 'g' to 'o')
proifts => profits   (transposition of 'if' to 'fi')
profits => profit    (deletion of 's')

Solution Stats

32.95% Correct | 67.05% Incorrect
Last Solution submitted on Jan 24, 2024

Problem Comments

Solution Comments

Show comments

Problem Recent Solvers25

Suggested Problems

More from this Author40

Community Treasure Hunt

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

Start Hunting!