Cody

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

Solution 1949786

Submitted on 26 Sep 2019 by Nikolaos Nikolaou
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

s1 = 'mom' s2 = 'dad' distance = 3

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

s1 = 'dogs' s2 = 'dog' distance = 1

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

s1 = 'true' s2 = 'true' distance = 0

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

s1 = 'true' s2 = 'false' distance = 4

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

s1 = 'abc' s2 = 'ca' distance = 3 distance = 2

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

s1 = 'tee' s2 = 'tree' distance = 1

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

s1 = 'email' s2 = 'mails' distance = 2

8   Pass

s1 = 'profit' s2 = 'gifts' distance = 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

s1 = 'wxckujc' s2 = 'nbfms' distance = 7 s1 = 'nbfms' s2 = 'wxckujc' distance = 7 s1 = 'gafk' s2 = 'ominno' distance = 6 s1 = 'ominno' s2 = 'gafk' distance = 6 s1 = 'tzfoywj' s2 = 'stcm' distance = 7 s1 = 'stcm' s2 = 'tzfoywj' distance = 7 s1 = 'jyqidg' s2 = 'hxcjp' distance = 6 s1 = 'hxcjp' s2 = 'jyqidg' distance = 6 s1 = 'ajzzmrfos' s2 = 'lotiybbumv' distance = 10 s1 = 'lotiybbumv' s2 = 'ajzzmrfos' distance = 10 s1 = 'gshjcclc' s2 = 'fhot' distance = 7 s1 = 'fhot' s2 = 'gshjcclc' distance = 7 s1 = 'lgbcksnoih' s2 = 'ixnwtsfzb' distance = 9 s1 = 'ixnwtsfzb' s2 = 'lgbcksnoih' distance = 9 s1 = 'sdyiryzddn' s2 = 'twcoxuwxm' distance = 10 s1 = 'twcoxuwxm' s2 = 'sdyiryzddn' distance = 10 s1 = 'cxscpax' s2 = 'mdch' distance = 6 s1 = 'mdch' s2 = 'cxscpax' distance = 6 s1 = 'dfscs' s2 = 'vzbntuoynf' distance = 10 s1 = 'vzbntuoynf' s2 = 'dfscs' distance = 10

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

s1 = 'ynzuzedf' s2 = 'giokfomq' distance = 8 s1 = 'giokfomq' s2 = 'jrvgipnq' distance = 7 s1 = 'jrvgipnq' s2 = 'ynzuzedf' distance = 8 s1 = 'ddoslbyk' s2 = 'aaumyjdt' distance = 8 s1 = 'aaumyjdt' s2 = 'bnpafl' distance = 8 s1 = 'bnpafl' s2 = 'ddoslbyk' distance = 8 s1 = 'ztlzpcmm' s2 = 'llyk' distance = 7 s1 = 'llyk' s2 = 'awkxjsvw' distance = 8 s1 = 'awkxjsvw' s2 = 'ztlzpcmm' distance = 8 s1 = 'wnxkohyxph' s2 = 'gwbuvuazw' distance = 10 s1 = 'gwbuvuazw' s2 = 'igfymnts' distance = 9 s1 = 'igfymnts' s2 = 'wnxkohyxph' distance = 10 s1 = 'vkdlglv' s2 = 'zsuan' distance = 7 s1 = 'zsuan' s2 = 'uslrinzr' distance = 6 s1 = 'uslrinzr' s2 = 'vkdlglv' distance = 8 s1 = 'yjlsbvy' s2 = 'btcqyxku' distance = 8 s1 = 'btcqyxku' s2 = 'lcsdy' distance = 7 s1 = 'lcsdy' s2 = 'yjlsbvy' distance = 5 s1 = 'wmoyqt' s2 = 'sspmprmkci' distance = 9 s1 = 'sspmprmkci' s2 = 'ttcijmzgde' distance = 10 s1 = 'ttcijmzgde' s2 = 'wmoyqt' distance = 9 s1 = 'ctsojj' s2 = 'rrkwbs' distance = 6 s1 = 'rrkwbs' s2 = 'vyvgqb' distance = 6 s1 = 'vyvgqb' s2 = 'ctsojj' distance = 6 s1 = 'ozbwlbi' s2 = 'zvxecpqo' distance = 8 s1 = 'zvxecpqo' s2 = 'ccmyddtl' distance = 8 s1 = 'ccmyddtl' s2 = 'ozbwlbi' distance = 8 s1 = 'ogkpqzw' s2 = 'lucg' distance = 7 s1 = 'lucg' s2 = 'uhovyh' distance = 6 s1 = 'uhovyh' s2 = 'ogkpqzw' distance = 7 s1 = 'uuqiopjf' s2 = 'ykmvvm' distance = 8 s1 = 'ykmvvm' s2 = 'nksvloooa' distance = 7 s1 = 'nksvloooa' s2 = 'uuqiopjf' distance = 8 s1 = 'cnjzgozrol' s2 = 'wgtp' distance = 9 s1 = 'wgtp' s2 = 'sxttsmxpge' distance = 8 s1 = 'sxttsmxpge' s2 = 'cnjzgozrol' distance = 10 s1 = 'eiiwqdzjtk' s2 = 'tivd' distance = 8 s1 = 'tivd' s2 = 'prjmysr' distance = 7 s1 = 'prjmysr' s2 = 'eiiwqdzjtk' distance = 10 s1 = 'zeozdzm' s2 = 'ntjvtn' distance = 7 s1 = 'ntjvtn' s2 = 'utaexpbd' distance = 7 s1 = 'utaexpbd' s2 = 'zeozdzm' distance = 8 s1 = 'kakoktesnd' s2 = 'irbckpom' distance = 9 s1 = 'irbckpom' s2 = 'fkhsdalo' distance = 8 s1 = 'fkhsdalo' s2 = 'kakoktesnd' distance = 9 s1 = 'zygsw' s2 = 'tokiqnylds' distance = 9 s1 = 'tokiqnylds' s2 = 'vkkisrcaz' distance = 8 s1 = 'vkkisrcaz' s2 = 'zygsw' distance = 8 s1 = 'avpsplg' s2 = 'nabgwpx' distance = 6 s1 = 'nabgwpx' s2 = 'flpuwtsdgy' distance = 9 s1 = 'flpuwtsdgy' s2 = 'avpsplg' distance = 8 s1 = 'mwrfv' s2 = 'xocwpzjtv' distance = 7 s1 = 'xocwpzjtv' s2 = 'cnxwyjo' distance = 7 s1 = 'cnxwyjo' s2 = 'mwrfv' distance = 6 s1 = 'zlknqy' s2 = 'wxvzram' distance = 7 s1 = 'wxvzram' s2 = 'bnzvkmap' distance = 6 s1 = 'bnzvkmap' s2 = 'zlknqy' distance = 6 s1 = 'loeneiuh' s2 = 'gmlp' distance = 8 s1 = 'gmlp' s2 = 'hdeid' distance = 5 s1 = 'hdeid' s2 = 'loeneiuh' distance = 6 s1 = 'hoknpdy' s2 = 'joiylewdx' distance = 7 s1 = 'joiylewdx' s2 = 'zbwmwectlc' distance = 9 s1 = 'zbwmwectlc' s2 = 'hoknpdy' distance = 10 s1 = 'mwns' s2 = 'ailh' distance = 4 s1 = 'ailh' s2 = 'tnjyjshfwv' distance = 9 s1 = 'tnjyjshfwv' s2 = 'mwns' distance = 9 s1 = 'aocanyysoh' s2 = 'ciqlhbmumr' distance = 10 s1 = 'ciqlhbmumr' s2 = 'khaxe' distance = 9 s1 = 'khaxe' s2 = 'aocanyysoh' distance = 9 s1 = 'xxhtij' s2 = 'cyzilgysdj' distance = 9 s1 = 'cyzilgysdj' s2 = 'eenqi' distance = 10 s1 = 'eenqi' s2 = 'xxhtij' distance = 5 s1 = 'mkqwrydqx' s2 = 'ppbxa' distance = 9 s1 = 'ppbxa' s2 = 'ouga' distance = 4 s1 = 'ouga' s2 = 'mkqwrydqx' distance = 9 s1 = 'hoveaf' s2 = 'ivau' distance = 4 s1 = 'ivau' s2 = 'nwxli' distance = 5 s1 = 'nwxli' s2 = 'hoveaf' distance = 6 s1 = 'vlbwvjkhpm' s2 = 'poxtguc' distance = 10 s1 = 'poxtguc' s2 = 'znsuwsyyf' distance = 9 s1 = 'znsuwsyyf' s2 = 'vlbwvjkhpm' distance = 10 s1 = 'tpek' s2 = 'hmjwemnd' distance = 7 s1 = 'hmjwemnd' s2 = 'tblcztiu' distance = 8 s1 = 'tblcztiu' s2 = 'tpek' distance = 7 s1 = 'clkpvvwk' s2 = 'quvcwprbw' distance = 8 s1 = 'quvcwprbw' s2 = 'gonqtsdlk' distance = 9 s1 = 'gonqtsdlk' s2 = 'clkpvvwk' distance = 8 s1 = 'aphisaoaa' s2 = 'xzpshwwp' distance = 8 s1 = 'xzpshwwp' s2 = 'tlhwlv' distance = 6 s1 = 'tlhwlv' s2 = 'aphisaoaa' distance = 8 s1 = 'bedp' s2 = 'zxchamr' distance = 7 s1 = 'zxchamr' s2 = 'vdhksy' distance = 6 s1 = 'vdhksy' s2 = 'bedp' distance = 6 s1 = 'qhfzykek' s2 = 'wrbjcttuze' distance = 10 s1 = 'wrbjcttuze' s2 = 'qgrqj' distance = 9 s1 = 'qgrqj' s2 = 'qhfzykek' distance = 7 s1 = 'xemijbch' s2 = 'tcbvcv' distance = 7 s1 = 'tcbvcv' s2 = 'myomdbk' distance = 7 s1 = 'myomdbk' s2 = 'xemijbch' distance = 7 s1 = 'trhmael' s2 = 'ldontad' distance = 7 s1 = 'ldontad' s2 = 'ummmnkec' distance = 7 s1 = 'ummmnkec' s2 = 'trhmael' distance = 6 s1 = 'azez' s2 = 'lqva' distance = 4 s1 = 'lqva' s2 = 'jvdkannab' distance = 8 s1 = 'jvdkannab' s2 = 'azez' distance = 8 s1 = 'rqmnytht' s2 = 'xewqbtx' distance = 7 s1 = 'xewqbtx' s2 = 'nbjygigre' distance = 9 s1 = 'nbjygigre' s2 = 'rqmnytht' distance = 9 s1 = 'msdlytevcd' s2 = 'qljvpppj' distance = 9 s1 = 'qljvpppj' s2 = 'uvijef' distance = 7 s1 = 'uvijef' s2 = 'msdlytevcd' distance = 9 s1 = 'asuwqadenb' s2 = 'idfi' distance = 9 s1 = 'idfi' s2 = 'zmeb' distance = 4 s1 = 'zmeb' s2 = 'asuwqadenb' distance = 8 s1 = 'ultygql' s2 = 'etry' distance = 6 s1 = 'etry' s2 = 'qioglaub' distance = 8 s1 = 'qioglaub' s2 = 'ultygql' distance = 8 s1 = 'mqiefwws' s2 = 'adna' distance = 8 s1 = 'adna' s2 = 'ucqyt' distance = 5 s1 = 'ucqyt' s2 = 'mqiefwws' distance = 8 s1 = 'wrxticysud' s2 = 'jbujlfq' distance = 10 s1 = 'jbujlfq' s2 = 'kvevcqek' distance = 8 s1 = 'kvevcqek' s2 = 'wrxticysud' distance = 9 s1 = 'lsabl' s2 = 'xgqsqgkitl' distance = 8 s1 = 'xgqsqgkitl' s2 = 'ijmvbfthdg' distance = 10 s1 = 'ijmvbfthdg' s2 = 'lsabl' distance = 9 s1 = 'mgnkbsh' s2 = 'tjlqprsnn' distance = 8 s1 = 'tjlqprsnn' s2 = 'azjlej' distance = 8 s1 = 'azjlej' s2 = 'mgnkbsh' distance = 7 s1 = 'conyc' s2 = 'sdzendruxw' distance = 9 s1 = 'sdzendruxw' s2 = 'cetjbywfrx' distance = 10 s1 = 'cetjbywfrx' s2 = 'conyc' distance = 8 s1 = 'wjznfg' s2 = 'ixttul' distance = 6 s1 = 'ixttul' s2 = 'vocveui' distance = 6 s1 = 'vocveui' s2 = 'wjznfg' distance = 7 s1 = 'ontlp' s2 = 'jkfdpxhkvl' distance = 9 s1 = 'jkfdpxhkvl' s2 = 'zejeekbq' distance = 9 s1 = 'zejeekbq' s2 = 'ontlp' distance = 8 s1 = 'bqzhnzmirh' s2 = 'poej' distance = 10 s1 = 'poej' s2 = 'swzpp' distance = 5 s1 = 'swzpp' s2 = 'bqzhnzmirh' distance = 9 s1 = 'qpxx' s2 = 'emko' distance = 4 s1 = 'emko' s2 = 'tqtqsrpt' distance = 8 s1 = 'tqtqsrpt' s2 = 'qpxx' distance = 7 s1 = 'jyqnytvyrt' s2 = 'tmypehpcxz' distance = 10 s1 = 'tmypehpcxz' s2 = 'kagzn' distance = 10 s1 = 'kagzn' s2 = 'jyqnytvyrt' distance = 10 s1 = 'cdqs' s2 = 'ojntapsmq' distance = 8 s1 = 'ojntapsmq' s2 = 'xtnqijkcg' distance = 8 s1 = 'xtnqijkcg' s2 = 'cdqs' distance = 8