Cody

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

Solution 2105400

Submitted on 25 Jan 2020 by Asif Newaz
This solution is locked. To view this solution, you need to provide a solution of the same size or smaller.

### Test Suite

Test Status Code Input and Output
1   Pass
assert(isequal(Damerau_Levenshtein('mom','dad'),3)); % 3 substitutions

y = 0 1 2 3 1 1 2 3 2 2 2 3 3 3 3 3

2   Pass
assert(isequal(Damerau_Levenshtein('dogs','dog'),1)); % 1 deletion

y = 0 1 2 3 4 1 0 1 2 3 2 1 0 1 2 3 2 1 0 1

3   Pass
assert(isequal(Damerau_Levenshtein('true','true'),0)); % identity

y = 0 1 2 3 4 1 0 1 2 3 2 1 0 1 2 3 2 1 0 1 4 3 2 1 0

4   Pass
assert(isequal(Damerau_Levenshtein('true','false'),4)); % 1 insertion, 3 substitutions

y = 0 1 2 3 4 1 1 2 3 4 2 2 2 3 4 3 3 3 3 4 4 4 4 4 4 5 5 5 5 4

5   Pass
assert(isequal(Damerau_Levenshtein('abc','ca'),2)); % 1 deletion, 1 transposition

6   Pass
assert(isequal(Damerau_Levenshtein('tee','tree'),1));

y = 0 1 2 3 1 0 1 2 2 1 1 2 3 2 1 1 4 3 2 1

7   Pass
assert(isequal(Damerau_Levenshtein('email','mails'),2));

y = 0 1 2 3 4 5 1 1 1 2 3 4 2 2 2 1 2 3 3 3 3 2 1 2 4 4 4 3 2 1 5 5 5 4 3 2

8   Pass
assert(isequal(Damerau_Levenshtein('profit','gifts'),5));

y = 0 1 2 3 4 5 6 1 1 2 3 4 5 6 2 2 2 3 4 4 5 3 3 3 3 3 4 5 4 4 4 4 4 4 4 5 5 5 5 5 5 5

9   Pass
% symmetry rnd=@()char(randi([97 122],1,randi([4 10]))); for k=1:10 str1=rnd(); str2=rnd(); a=Damerau_Levenshtein(str1,str2); b=Damerau_Levenshtein(str2,str1); assert(isequal(a,b)) end

y = 0 1 2 3 4 5 1 1 2 3 4 5 2 2 2 3 4 5 3 3 3 3 4 5 4 4 4 4 4 5 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 8 8 8 8 8 8 y = 0 1 2 3 4 5 6 7 8 1 1 2 3 4 5 6 7 8 2 2 2 3 4 5 6 7 8 3 3 3 3 4 5 6 7 8 4 4 4 4 4 5 6 7 8 5 5 5 5 5 5 6 7 8 y = 0 1 2 3 4 1 1 2 3 4 2 1 2 3 4 3 2 2 2 3 4 3 3 3 3 5 4 4 4 4 6 5 5 5 5 7 6 6 6 6 8 7 7 7 7 9 8 8 8 8 y = 0 1 2 3 4 5 6 7 8 9 1 1 1 2 3 4 5 6 7 8 2 2 2 2 3 4 5 6 7 8 3 3 3 2 3 4 5 6 7 8 4 4 4 3 3 4 5 6 7 8 y = 0 1 2 3 4 5 6 7 8 9 1 1 2 3 4 4 5 6 7 8 2 2 2 3 4 5 5 6 7 8 3 3 3 3 4 5 6 6 7 8 4 4 4 4 4 5 6 7 7 8 5 5 5 5 5 5 6 7 8 8 6 6 6 6 6 6 6 7 8 9 7 6 7 7 7 7 7 7 8 9 8 7 7 8 8 8 7 8 8 9 9 8 8 8 9 9 8 8 9 9 10 9 9 9 9 10 9 8 9 10 y = 0 1 2 3 4 5 6 7 8 9 10 1 1 2 3 4 5 6 6 7 8 9 2 2 2 3 4 5 6 7 7 8 9 3 3 3 3 4 5 6 7 8 8 9 4 4 4 4 4 5 6 7 8 9 9 5 4 5 5 5 5 6 7 8 9 10 6 5 5 6 6 6 6 7 7 8 9 7 6 6 6 7 7 7 7 8 8 8 8 7 7 7 7 8 8 8 8 9 9 9 8 8 8 8 8 9 9 9 9 10 y = 0 1 2 3 4 5 6 1 1 2 3 4 5 6 2 2 2 3 4 5 6 3 3 3 3 4 5 6 4 4 4 4 4 5 6 5 5 5 5 5 5 5 y = 0 1 2 3 4 5 1 1 2 3 4 5 2 2 2 3 4 5 3 3 3 3 4 5 4 4 4 4 4 5 5 5 5 5 5 5 6 6 6 6 6 5 y = 0 1 2 3 4 5 6 7 8 9 1 0 1 2 3 4 5 6 7 8 2 1 1 2 3 4 5 6 7 8 3 2 2 2 3 4 5 6 7 8 4 3 3 3 3 4 4 5 6 7 5 4 4 4 4 4 5 4 5 6 6 5 5 5 5 5 5 5 5 6 7 6 6 6 6 6 6 6 6 6 8 7 7 7 7 7 7 7 6 7 9 8 8 8 8 8 8 8 7 7 10 9 9 9 9 9 9 9 8 7 y = 0 1 2 3 4 5 6 7 8 9 10 1 0 1 2 3 4 5 6 7 8 9 2 1 1 2 3 4 5 6 7 8 9 3 2 2 2 3 4 5 6 7 8 9 4 3 3 3 3 4 5 6 7 8 9 5 4 4 4 4 4 5 6 7 8 9 6 5 5 5 4 5 5 6 7 8 9 7 6 6 6 5 4 5 6 7 8 9 8 7 7 7 6 5 5 6 6 7 8 9 8 8 8 7 6 6 6 7 7 7 y = 0 1 2 3 4 5 6 1 1 2 3 4 5 6 2 2 2 2 3 4 5 3 2 3 3 3 4 5 4 3 3 4 4 4 4 5 4 4 4 5 5 5 6 5 5 4 5 6 6 y = 0 1 2 3 4 5 6 1 1 2 2 3 4 5 2 2 2 3 3 4 5 3 3 2 3 4 4 4 4 4 3 3 4 5 5 5 5 4 4 4 5 6 6 6 5 5 4 5 6 y = 0 1 2 3 4 5 6 7 8 9 1 1 2 3 4 5 6 7 8 9 2 2 2 3 4 5 6 7 8 9 3 3 3 3 4 5 5 6 7 8 4 4 4 4 4 5 6 6 7 8 5 5 5 5 5 5 6 7 7 8 6 6 6 6 6 6 5 6 7 8 7 7 7 7 7 7 6 6 7 8 8 8 8 8 8 8 7 7 7 8 y = 0 1 2 3 4 5 6 7 8 1 1 2 3 4 5 6 7 8 2 2 2 3 4 5 6 7 8 3 3 3 3 4 5 6 7 8 4 4 4 4 4 5 6 7 8 5 5 5 5 5 5 6 7 8 6 6 6 5 6 6 5 6 7 7 7 7 6 6 7 6 6 7 8 8 8 7 7 7 7 7 7 9 9 9 8 8 8 8 8 8 y = 0 1 2 3 4 5 1 1 2 3 4 5 2 2 2 3 4 5 3 3 3 2 3 4 4 4 4 3 3 4 y = 0 1 2 3 4 1 1 2 3 4 2 2 2 3 4 3 3 3 2 3 4 4 4 3 3 5 5 5 4 4 y = 0 1 2 3 4 5 6 7 1 1 2 3 3 4 5 6 2 2 2 3 4 4 5 6 3 3 3 3 4 5 5 6 4 4 4 4 4 5 6 6 5 5 5 5 5 5 6 7 6 6 6 6 6 6 6 7 7 7 6 7 7 7 7 7 y = 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 2 2 2 3 4 5 6 6 3 3 3 3 4 5 6 7 4 3 4 4 4 5 6 7 5 4 4 5 5 5 6 7 6 5 5 5 6 6 6 7 7 6 6 6 6 7 7 7 y = 0 1 2 3 4 5 1 1 2 3 4 5 2 2 2 3 4 5 3 3 3 2 3 4 4 4 4 3 3 4 5 5 5 4 4 4 6 6 6 5 5 5 7 7 7 6 6 6 8 8 8 7 7 7 9 9 9 8 8 8 y = 0 1 2 3 4 5 6 7 8 9 1 1 2 3 4 5 6 7 8 9 2 2 2 3 4 5 6 7 8 9 3 3 3 2 3 4 5 6 7 8 4 4 4 3 3 4 5 6 7 8 5 5 5 4 4 4 5 6 7 8

10   Pass
% trinagle inequality rnd=@()char(randi([97 122],1,randi([4 10]))); for k=1:50 str1=rnd(); str2=rnd(); str3=rnd(); a=Damerau_Levenshtein(str2,str3); b=Damerau_Levenshtein(str3,str1); c=Damerau_Levenshtein(str1,str2); assert(a+b>=c) end

y = 0 1 2 3 4 5 6 1 1 2 2 3 4 5 2 2 2 3 3 4 5 3 3 3 3 4 4 5 4 4 4 4 4 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 y = 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 2 2 2 3 4 5 6 7 3 3 3 3 4 5 6 7 4 4 4 4 4 5 5 6 5 5 5 5 4 5 6 5 6 6 6 6 5 5 6 6 y = 0 1 2 3 4 5 6 1 1 1 2 3 4 5 2 2 2 2 3 4 5 3 3 3 3 3 4 5 4 4 4 4 4 4 5 5 5 5 5 5 5 5 6 5 6 6 6 6 5 y = 0 1 2 3 4 5 6 7 8 9 10 1 1 2 3 4 5 6 7 8 9 10 2 2 2 3 4 5 6 7 8 9 10 3 3 2 3 4 5 6 7 8 9 10 4 4 3 3 4 5 6 7 8 9 10 5 5 4 4 4 5 6 7 8 9 9 6 6 5 5 5 5 6 7 8 9 10 7 7 6 6 6 6 5 6 7 8 9 8 7 7 7 7 7 6 6 7 8 9 y = 0 1 2 3 4 5 6 7 8 1 1 2 3 4 5 6 7 8 2 2 2 3 4 5 6 7 8 3 3 3 3 3 4 5 6 7 4 4 4 4 4 4 4 5 6 5 5 5 5 5 5 5 5 6 y = 0 1 2 3 4 5 1 1 2 3 4 5 2 2 2 3 4 5 3 3 3 3 4 5 4 4 4 4 4 5 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 8 7 8 8 8 8 9 8 8 9 9 9 10 9 9 9 10 10 y = 0 1 2 3 4 5 6 1 1 2 3 4 5 6 2 2 2 3 4 5 6 3 3 3 3 4 5 6 4 3 4 4 4 5 6 5 4 4 5 5 5 6 6 5 5 5 6 6 6 7 6 6 6 6 7 7 8 7 6 7 7 7 8 y = 0 1 2 3 4 5 6 7 8 1 1 2 3 4 5 6 7 8 2 2 2 3 4 5 6 7 8 3 3 3 3 4 5 6 7 8 4 4 4 4 4 5 6 7 8 5 5 5 5 5 5 6 7 8 y = 0 1 2 3 4 5 1 1 2 3 4 5 2 2 2 3 4 5 3 3 3 3 4 5 4 4 4 4 4 5 5 4 5 5 5 5 6 5 5 6 6 6 y = 0 1 2 3 4 5 6 1 1 2 3 4 5 6 2 2 2 3 4 5 6 3 3 2 3 4 5 6 4 4 3 3 4 5 6 5 5 4 4 4 5 6 6 6 5 5 5 5 6 7 7 6 6 6 6 6 y = 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 6 2 2 2 3 4 5 6 7 3 3 3 3 4 5 6 7 4 4 4 4 4 5 6 7 y = 0 1 2 3 4 1 1 2 3 4 2 2 2 3 4 3 3 3 3 4 4 4 4 4 3 5 5 5 5 4 6 6 6 6 5 y = 0 1 2 3 4 1 1 2 3 4 2 2 2 3 4 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 y = 0 1 2 3 4 5 1 1 2 3 3 4 2 2 2 3 4 4 3 3 3 3 4 5 4 4 4 4 4 5 5 5 5 5 5 5 y = 0 1 2 3 4 5 1 1 1 2 3 4 2 2 2 2 3 4 3 3 3 2 3 4 4 4 4 3 3 4 y = 0 1 2 3 4 1 1 2 3 4 2 2 2 3 4 3 3 2 3 4 4 4 3 3 4 5 5 4 4 4 6 6 5 5 5 7 7 6 6 6 8 8 7 7 7 y = 0 1 2 3 4 5 6 7 8 1 1 2 3 4 5 6 7 8 2 2 2 3 4 5 6 7 8 3 3 3 3 4 5 6 7 8 4 4 4 4 4 5 6 7 8 5 4 5 5 4 5 6 7 8 y = 0 1 2 3 4 5 1 0 1 2 3 4 2 1 1 2 3 4 3 2 2 2 3 4 4 3 3 3 3 4 y = 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 2 2 2 3 4 5 6 7 3 3 3 3 4 5 6 7 4 4 4 4 4 4 5 6 y = 0 1 2 3 4 1 1 2 3 4 2 2 2 3 4 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 y = 0 1 2 3 4 5 1 1 2 3 4 5 2 2 2 3 4 5 3 3 3 3 4 5 4 4 4 4 4 5 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7 y = 0 1 2 3 4 5 6 7 1 1 2 3 4 5 6 7 2 2 2 3 4 5 6 7 3 3 3 3 4 5 6 7 4 4 4 4 4 5 6 6 5 5 5 4 5 5 6 7 6 6 6 5 5 6 5 6 7 7 7 6 6 6 6 6 8 8 8 7 7 7 7 7 9 9 9 8 8 8 8 8 10 10 10 9 9 9 9 8 y = 0 1 2 3 4 5 6 7 8 9 10 1 1 2 3 4 5 6 7 8 9 10 2 2 2 3 4 5 6 7 8 9 10 3 3 3 3 4 5 6 7 8 9 10 4 4 3 4 4 5 6 7 8 9 10 5 5 4 4 5 4 5 6 7 8 9 6 5 5 5 5 5 5 6 7 8 9 7 6 6 6 6 6 6 6 7 8 9 8 7 7 7 7 7 7 7 7 8 9 y = 0 1 2 3 4 5 6 7 8 1 0 1 2 3 4 5 6 7 2 1 1 2 3 4 5 6 7 3 2 2 2 3 3 4 5 6 4 3 2 3 3 4 4 5 6 5 4 3 3 4 4 5 5 6 6 5 4 4 4 5 5 6 6 7 6 5 5 5 5 6 6 7 y = 0 1 2 3 4 5 6 7 8 9 1 1 2 3 4 5 6 7 8 9 2 1 2 3 4 5 6 7 8 9 3 2 2 3 4 5 6 7 8 9 4 3 3 3 4 5 6 7 8 9 5 4 4 4 4 5 6 7 8 9 6 5 5 5 5 5 6 7 8 9 7 6 6 6 6 6 6 7 8 9 8 7 7 7 7 7 7 7 8 9 9 8 8 8 8 8 8 8 8 9 10 9 9 9 9 9 9 9 9 9 y = 0 1 2 3 4 5 6 7 8 9 10 1 1 2 3 4 5 6 7 8 9 10 2 2 2 3 4 5 6 7 8 9 10 3 3 3 3 4 5 6 7 8 9 10 4 4 4 4 4 5 6 7 8 9 10 5 5 5 5 5 5 6 7 8 9 9 6 6 6 6 6 6 6 7 8 9 10 7 7 7 7 7 7 7 7 8 9 10 8 8 8 8 8 8 8 8 8 9 10 y = 0 1 2 3 4 5 6 7 8 1 1 2 3 4 5 6 7 8 2 2 2 3 4 5 6 7 8 3 3 3 3 4 5 6 7 8 4 4 4 4 4 5 6 7 8 5 5 5 5 5 5 6 7 8 6 6 6 6 6 6 6 7 8 7 7 7 7 7 7 7 7 8 8 8 8 8 8 8 8 8 8 9 9 9 8 9 9 9 9 9 y = 0 1 2 3 4 5 6 7 8 1 1 2 3 4 5 6 7 8 2 2 2 3 4 5 6 7 8 3 ...