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
Problem Comments
-
4 Comments
i am facing a problem with ur test suite 5. is it correct?
even the built-in matlab function 'edit distance' is giving the result 3.
which i believe is the correct one.
if i am not wrong, according to demarau algorithm - here transposition will not occur.
Test case #5 is correct, Asif. If you want, you can try it on wolfram alpha using DamerauLevenshteinDistance['abc','ca']. Be careful, because the algorithm from wikipedia has errors.
Another example that should return 2 via Damerou-Levenshtein and 3 via Levenshtein alone: 'jellyfish' and 'jellyifhs'.
The algorithm given by Wikipedia is correct, I think, but take note that the first algorithm Wikipedia gives does not actually compute the Damerau-Levenshtein distance, but rather a related metric. Confusing, but the entry says as much if you read it closely.
Solution Comments
Show commentsProblem Recent Solvers25
Suggested Problems
-
42103 Solvers
-
Back to basics 23 - Triangular matrix
1003 Solvers
-
Find out the Gray Code for a Given Binary Number
106 Solvers
-
49 Solvers
-
Legend of Zelda - Rupee Count (Item Purchase)
36 Solvers
More from this Author40
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!