Cody

# Problem 93. Calculate the Levenshtein distance between two strings

Solution 2098892

Submitted on 19 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
s1 = 'kitten'; s2 = 'sitting'; d_correct = 3; assert(isequal(levenshtein(s1,s2),d_correct))

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

2   Pass
s1 = 'Saturday'; s2 = 'Sunday'; d_correct = 3; assert(isequal(levenshtein(s1,s2),d_correct))

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

3   Pass
s1 = 'MATLAB rocks!'; s2 = 'MathWorks'; d_correct = 9; assert(isequal(levenshtein(s1,s2),d_correct))

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

4   Pass
s1 = 'Four score and seven years ago'; s2 = 'Eighty seven years before today'; d_correct = 25; assert(isequal(levenshtein(s1,s2),d_correct))

y = Columns 1 through 30 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 2 2 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 3 3 3 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 28 4 4 4 4 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 5 5 5 5 5 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 6 6 6 6 6 6 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 21 22 23 24 25 26 27 28 7 7 7 7 7 6 7 7 8 9 10 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 25 26 27 8 8 8 8 8 7 6 7 8 9 10 11 11 12 13 14 14 15 16 17 18 19 20 21 22 23 24 25 26 27 9 9 9 9 9 8 7 7 8 9 9 10 11 12 13 14 15 14 15 16 17 18 19 20 21 22 23 24 25 26 10 10 10 10 10 9 8 8 8 9 10 10 11 12 13 14 15 15 14 15 16 17 18 19 20 21 22 23 24 25 11 11 11 11 11 10 9 9 9 9 9 10 11 12 13 14 15 15 15 14 15 16 17 18 19 20 21 22 23 24 12 12 12 12 12 11 10 10 10 10 10 10 11 11 12 13 14 15 16 15 14 15 16 17 18 19 20 21 22 23 13 13 13 13 13 12 11 11 11 11 11 10 11 12 12 12 13 14 15 16 15 14 15 16 17 18 19 20 21 22 14 14 14 14 14 13 12 12 12 12 12 11 11 12 13 13 13 14 15 16 16 15 14 15 16 17 18 19 20 21 15 15 15 15 15 14 13 13 13 13 12 12 12 12 13 14 14 13 14 15 16 16 15 14 15 16 17 18 19 20 16 16 16 16 16 15 14 14 14 14 13 13 12 13 13 14 15 14 14 15 16 17 16 15 14 15 16 17 18 19 17 17 17 17 16 16 15 15 15 14 14 14 13 13 14 14 15 15 15 15 16 17 17 16 15 14 15 16 17 18 18 18 18 18 17 17 16 16 16 15 15 15 14 14 14 15 14 15 16 16 16 17 18 17 16 15 14 15 16 17 19 19 19 19 18 17 17 17 17 16 16 15 15 15 15 14 15 15 16 17 17 16 17 18 17 16 15 14 15 16 20 20 20 20 19 18 18 18 18 17 17 16 16 16 16 15 15 16 16 17 18 17 17 18 18 17 16 15 15 16 21 21 21 21 20 19 19 19 19 18 17 17 17 17 17 16 16 15 16 16 17 18 18 17 18 18 17 16 16 16 22 22 22 22 21 20 20 20 20 19 18 18 18 18 18 17 17 16 16 17 17 18 19 18 18 19 18 17 17 17 23 23 22 23 22 21 21 21 20 20 19 19 19 19 19 18 18 17 17 17 18 18 19 19 19 19 19 18 18 18 24 24 23 23 23 22 22 22 21 20 20 20 20 20 20 19 19 18 18 18 18 19 19 20 20 19 20 19 19 19 25 25 24 24 24 23 23 23 22 21 20 21 21 21 21 20 20 19 19 18 19 19 20 19 20 20 20 20 20 20 26 26 25 25 25 24 24 24 23 22 21 20 21 22 22 21 21 20 20 19 19 19 20 20 20 21 21 20 21 21 27 27 26 26 26 25 25 25 24 23 22 21 21 22 23 22 22 21 21 20 20 20 20 21 21 21 22 21 21 22 28 28 27 27 27 26 26 26 25 24 23 22 22 22 23 23 23 22 22 21 21 21 21 21 22 22 22 22 22 22 29 29 28 28 28 27 27 27 26 25 24 23 23 23 22 23 24 23 23 22 22 22 22 22 22 23 23 23 23 23 30 30 29 29 29 28 28 28 27 26 25 24 23 24 23 23 24 24 24 23 23 23 23 23 22 23 24 24 23 24 31 31 30 30 30 29 29 29 28 27 26 25 24 24 24 24 24 25 25 24 24 24 23 24 23 23 24 25 24 24 Column 31 30 30 30 29 29 30 29 28 28 27 26 25 24 23 22 21 20 19 18 17 17 17 17 17 18 19 20 21 22 23 24 25

5   Pass
s1 = 'Row row row your boat'; s2 = 'Gently down the stream'; d_correct = 18; assert(isequal(levenshtein(s1,s2),d_correct))

y = 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2 2 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 3 3 3 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 4 4 4 4 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 20 5 5 5 5 5 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 6 6 6 6 6 6 6 7 8 9 10 11 12 12 13 14 15 16 17 18 19 20 7 7 7 7 6 7 7 7 7 8 9 10 11 12 13 14 15 15 16 17 18 19 8 8 8 8 7 7 8 8 8 8 9 10 11 12 13 14 15 16 16 17 18 19 9 9 8 9 8 8 7 8 9 9 8 9 10 11 12 13 14 15 16 16 17 18 10 10 9 8 9 9 8 7 8 9 9 8 9 10 11 12 13 14 15 16 17 18 11 11 10 9 9 10 9 8 8 9 10 9 9 10 11 12 13 14 15 16 17 18 12 12 11 10 9 10 10 9 8 9 10 10 9 10 11 12 13 13 14 15 16 17 13 13 12 11 10 10 11 10 9 9 10 11 10 10 11 12 13 14 14 15 16 16 14 14 13 12 11 11 11 11 10 10 10 11 11 11 11 12 13 14 15 15 16 17 15 15 14 13 12 12 12 12 11 11 11 11 12 12 12 12 13 14 15 16 16 17 16 16 15 14 13 13 13 13 12 12 12 12 11 12 13 13 13 13 14 15 16 17 17 17 16 15 14 14 14 14 13 13 13 13 12 12 13 14 14 14 14 15 16 17 18 18 17 16 15 15 15 15 14 14 14 14 13 13 13 14 15 15 15 15 16 16 19 19 18 17 16 15 16 16 15 14 15 15 14 14 14 14 14 15 16 16 16 17 20 20 19 18 17 16 16 17 16 15 15 16 15 15 15 15 15 15 16 17 17 17 21 21 20 19 18 17 17 17 17 16 16 16 16 16 16 16 16 16 16 17 17 18 22 22 21 20 19 18 18 18 18 17 17 17 17 17 17 17 17 17 17 17 18 18

6   Pass
s1 = 'ninety-nine bottles of beer on the wall'; s2 = 'eighty-six bottles of beer on the wall'; d_correct = 6; assert(isequal(levenshtein(s1,s2),d_correct))

y = Columns 1 through 30 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 1 1 2 3 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 2 2 1 2 3 4 5 6 7 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 3 3 2 2 3 4 5 6 7 8 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 4 4 3 3 3 4 5 6 7 8 9 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 5 5 4 4 4 3 4 5 6 7 8 9 10 11 12 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 6 6 5 5 5 4 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 7 7 6 6 6 5 4 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 8 8 7 7 7 6 5 4 4 5 6 7 8 9 10 11 12 13 14 14 15 16 17 18 19 20 21 22 23 24 9 9 8 8 8 7 6 5 5 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 10 10 9 9 9 8 7 6 6 5 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 11 11 10 10 10 9 8 7 7 6 6 6 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 12 12 11 11 11 10 9 8 8 7 7 7 7 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 13 13 12 12 12 11 10 9 9 8 8 8 8 7 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 14 14 13 13 13 12 11 10 10 9 9 9 9 8 7 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 15 15 14 14 14 13 12 11 11 10 10 10 10 9 8 7 6 7 8 9 10 11 12 13 14 15 16 17 18 19 16 16 15 15 15 14 13 12 12 11 11 11 11 10 9 8 7 6 7 8 9 10 11 12 13 14 15 16 17 18 17 17 16 16 15 15 14 13 13 12 12 11 12 11 10 9 8 7 6 7 8 9 10 11 12 13 14 15 16 17 18 18 17 17 16 16 15 14 14 13 13 12 12 12 11 10 9 8 7 6 7 8 9 10 11 12 13 14 15 16 19 19 18 18 17 17 16 15 15 14 14 13 12 13 12 11 10 9 8 7 6 7 8 9 10 11 12 13 14 15 20 20 19 19 18 18 17 16 16 15 15 14 13 13 13 12 11 10 9 8 7 6 7 8 9 10 11 12 13 14 21 21 20 20 19 19 18 17 17 16 16 15 14 14 14 13 12 11 10 9 8 7 6 7 8 9 10 11 12 13 22 22 21 21 20 20 19 18 18 17 17 16 15 15 15 14 13 12 11 10 9 8 7 6 7 8 9 10 11 12 23 23 22 22 21 21 20 19 19 18 18 17 16 15 16 15 14 13 12 11 10 9 8 7 6 7 8 9 10 11 24 24 23 23 22 22 21 20 20 19 19 18 17 16 16 16 15 14 13 12 11 10 9 8 7 6 7 8 9 10 25 25 24 24 23 23 22 21 21 20 20 19 18 17 17 17 16 15 14 13 12 11 10 9 8 7 6 7 8 9 26 26 25 25 24 24 23 22 22 21 21 20 19 18 18 18 17 16 15 14 13 12 11 10 9 8 7 6 7 8 27 27 26 26 25 25 24 23 23 22 22 21 20 19 19 19 18 17 16 15 14 13 12 11 10 9 8 7 6 7 28 28 27 27 26 26 25 24 24 23 23 22 21 20 19 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 29 28 28 27 27 27 26 25 24 24 23 23 22 21 20 20 20 19 18 17 16 15 14 13 12 11 10 9 8 7 30 29 29 28 28 28 27 26 25 25 24 24 23 22 21 21 21 20 19 18 17 16 15 14 13 12 11 10 9 8 31 30 30 29 29 28 28 27 26 26 25 25 24 23 22 21 21 21 20 19 18 17 16 15 14 13 12 11 10 9 32 31 31 30 30 29 29 28 27 27 26 26 25 24 23 22 22 22 21 20 19 18 17 16 15 14 13 12 11 10 33 32 32 31 30 30 30 29 28 28 27 26 26 25 24 23 23 23 22 21 20 19 18 17 16 15 14 13 12 11 34 33 33 32 31 31 31 30 29 29 28 27 26 26 25 24 24 24 23 22 21 20 19 18 17 16 15 14 13 12 35 34 34 33 32 32 32 31 30 30 29 28 27 27 26 25 25 25 24 23 22 21 20 19 18 17 16 15 14 13 36 35 35 34 33 33 33 32 31 31 30 29 28 28 27 26 26 26 25 24 23 22 21 20 19 18 17 16 15 14 37 36 36 35 34 34 34 33 32 32 31 30 29 29 28 27 27 26 26 25 24 23 22 21 20 19 18 17 16 15 38 37 37 36 35 35 35 34 33 33 32 31 30 30 29 28 28 27 27 26 25 24 23 22 21 20 19 18 17 16 Columns 31 through 40 30 31 32 33 34 35 36 37 38 39 29 30 31 32 33 34 35 36 37 38 28 29 30 31 32 33 34 35 36 37 28 29 30 31 32 33 34 35 36 37 28 29 30 30 31 32 33 34 35 36 27 28 29 30 31 32 33 34 35 36 27 28 29 30 31 32 33 34 35 36 26 27 28 29 30 31 32 33 34 35 25 26 27 28 29 30 31 32 33 34 25 26 27 28 29 30 31 32 33 34 25 26 27 28 29 30 31 32 33 34 24 25 26 27 28 29 30 31 32 33 23 24 25 26 27 28 29 30 31 32 22 23 24 25 26 27 28 29 30 31 21 22 23 24 25 26 27 28 29 30 20 21 22 23 24 25 26 27 28 29 19 20 21 22 23 24 25 26 27 28 18 19 20 21 22 23 24 25 26 27 17 18 19 20 21 22 23 24 25 26 16 17 18 19 20 21 22 23 24 25 15 16 17 18 19 20 21 22 23 24 14 15 16 17 18 19 20 21 22 23 13 14 15 16 17 18 19 20 21 22 12 13 14 15 16 17 18 19 20 21 11 12 13 14 15 16 17 18 19 20 10 11 12 13 14 15 16 17 18 19 9 10 11 12 13 14 15 16 17 18 8 9 10 11 12 13 14 15 16 17 7 8 9 10 11 12 13 14 15 16 6 7 8 9 10 11 12 13 14 15 7 6 7 8 9 10 11 12 13 14 8 7 6 7 8 9 10 11 12 13 9 8 7 6 7 8 9 10 11 12 10 9 8 7 6 7 8 9 10 11 11 10 9 8 7 6 7 8 9 10 12 11 10 9 8 7 6 7 8 9 13 12 11 10 9 8 7 6 7 8 14 13 12 11 10 9 8 7 6 7 15 14 13 12 11 10 9 8 7 6

7   Pass
s1 = 'these are the times that try men''s souls'; s2 = 'soulwise, these are trying times'; d_correct = 27; assert(isequal(levenshtein(s1,s2),d_correct))

y = Columns 1 through 30 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 1 1 2 3 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 2 2 2 3 4 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 3 3 3 3 4 5 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 4 4 4 4 4 5 6 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 5 5 5 5 5 5 6 7 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 6 6 6 6 6 6 6 7 8 8 9 10 11 12 13 14 14 15 16 17 18 19 20 21 22 23 24 25 26 27 7 7 7 7 6 7 7 7 8 9 9 10 11 12 13 14 15 15 16 16 17 18 19 20 21 22 23 24 25 26 8 8 8 7 7 6 7 8 8 8 9 10 11 11 12 13 14 15 15 16 17 18 19 20 21 22 23 24 25 26 9 9 9 8 8 7 7 8 9 9 9 10 11 12 12 13 14 15 16 16 17 18 19 20 21 22 23 24 25 26 10 10 10 9 9 8 7 8 9 10 9 10 11 12 12 13 14 15 16 17 16 17 18 19 20 21 22 23 24 25 11 10 11 10 10 9 8 8 9 10 10 9 10 11 12 12 13 14 15 16 17 16 17 18 19 20 21 22 23 24 12 11 10 11 11 10 9 9 9 10 11 10 9 10 11 12 13 14 15 16 17 17 16 17 18 19 20 21 22 23 13 12 11 10 11 11 10 10 10 9 10 11 10 9 10 11 12 13 14 15 16 17 17 17 18 19 20 21 22 23 14 13 12 11 10 11 11 11 11 10 10 11 11 10 10 11 12 13 14 14 15 16 17 18 18 19 20 21 22 23 15 14 13 12 11 10 11 12 12 11 11 11 12 11 11 11 12 13 13 14 15 16 17 18 19 19 20 21 22 23 16 15 14 13 12 11 10 11 12 12 11 12 12 12 11 12 12 13 14 14 14 15 16 17 18 19 20 21 22 22 17 16 15 14 13 12 11 10 11 12 12 12 13 13 12 12 13 13 14 15 15 15 16 16 17 18 19 20 21 22 18 17 16 15 14 13 12 11 10 11 12 13 13 14 13 13 13 14 14 15 16 16 16 17 17 18 19 19 20 21 19 18 17 16 15 14 13 12 11 10 11 12 13 13 14 14 14 14 14 15 16 17 17 17 18 18 19 20 20 21 20 19 18 17 16 15 14 13 12 11 10 11 12 13 13 14 15 15 15 15 15 16 17 18 18 18 19 20 21 20 21 20 19 18 17 16 15 14 13 12 11 10 11 12 13 13 14 15 16 16 16 15 16 17 18 19 18 19 20 21 22 21 20 19 18 17 16 15 14 13 12 11 11 12 13 14 14 15 16 17 17 16 16 17 18 19 19 18 19 20 23 22 21 20 19 18 17 16 15 14 13 12 12 12 13 14 15 15 16 17 18 17 17 17 18 19 20 19 18 19 24 23 22 21 20 19 18 17 16 15 14 13 13 13 13 14 14 15 16 17 18 18 18 18 18 19 20 20 19 19 25 24 23 22 21 20 19 18 17 16 15 14 14 14 14 14 15 15 16 17 18 19 19 19 19 19 20 21 20 20 26 25 24 23 22 21 20 19 18 17 16 15 15 15 15 15 15 16 16 17 18 19 20 20 20 20 20 21 21 21 27 26 25 24 23 22 21 20 19 18 17 16 16 16 15 16 16 16 17 17 17 18 19 20 21 20 21 21 22 21 28 27 26 25 24 23 22 21 20 19 18 17 17 17 16 15 16 17 17 18 18 17 18 19 20 21 20 21 22 22 29 28 27 26 25 24 23 22 21 20 19 18 18 18 17 16 15 16 17 18 19 18 18 19 20 21 21 21 22 23 30 29 28 27 26 25 24 23 22 21 20 19 19 19 18 17 16 15 16 17 18 19 19 19 20 21 22 22 22 23 31 30 29 28 27 26 25 24 23 22 21 20 20 19 19 18 17 16 15 16 17 18 19 20 20 21 22 23 23 23 32 31 30 29 28 27 26 25 24 23 22 21 21 20 20 19 18 17 16 15 16 17 18 19 20 21 22 23 24 24 Columns 31 through 41 30 31 32 33 34 35 36 37 38 39 40 29 30 31 32 33 34 35 36 37 38 39 29 30 31 32 33 34 35 35 36 37 38 29 30 31 32 33 34 35 36 35 36 37 29 30 31 32 33 34 35 36 36 35 36 29 30 31 32 33 34 35 36 37 36 36 28 29 30 31 32 33 34 35 36 37 37 27 28 29 30 31 32 33 34 35 36 37 27 27 28 29 30 31 32 33 34 35 36 27 28 28 29 30 31 32 33 34 35 36 26 27 28 29 30 30 31 32 33 34 35 25 26 27 28 29 30 31 32 33 34 35 24 25 26 27 28 29 30 31 32 33 34 24 24 25 26 27 28 29 30 31 32 33 24 25 25 26 26 27 28 29 30 31 32 24 24 25 26 27 27 28 29 30 31 32 23 24 25 26 27 27 28 29 30 31 32 23 24 25 26 27 28 28 29 30 31 32 22 23 24 25 26 27 28 29 30 31 32 22 22 23 24 25 26 27 28 29 30 31 21 22 23 24 25 25 26 27 28 29 30 21 22 23 24 25 26 26 27 28 29 30 21 22 23 24 25 26 27 27 28 29 30 20 21 22 23 24 25 26 27 28 29 30 20 21 22 23 24 25 26 27 28 29 30 20 21 21 22 23 24 25 26 27 28 29 21 21 22 22 23 24 25 26 27 28 29 22 22 22 23 23 23 24 25 26 27 28 22 23 23 23 24 24 24 25 26 27 28 23 23 24 24 24 25 25 25 26 27 28 23 24 24 25 25 25 26 26 26 27 28 24 23 24 25 26 26 26 27 27 27 28 24 24 24 25 25 26 26 27 28 28 27