Cody

Problem 93. Calculate the Levenshtein distance between two strings

Solution 409118

Submitted on 24 Feb 2014 by Axel
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))

ans = 0 1 2 3 4 5 6 7 u = 0 1 2 3 4 5 6 7 i = 1 ans = 1 1 ans = 1 1 2 ans = 1 1 2 3 ans = 1 1 2 3 4 ans = 1 1 2 3 4 5 ans = 1 1 2 3 4 5 6 ans = 1 1 2 3 4 5 6 7 u = 1 1 2 3 4 5 6 7 i = 2 ans = 2 2 ans = 2 2 1 ans = 2 2 1 2 ans = 2 2 1 2 3 ans = 2 2 1 2 3 4 ans = 2 2 1 2 3 4 5 ans = 2 2 1 2 3 4 5 6 u = 2 2 1 2 3 4 5 6 i = 3 ans = 3 3 ans = 3 3 2 ans = 3 3 2 1 ans = 3 3 2 1 2 ans = 3 3 2 1 2 3 ans = 3 3 2 1 2 3 4 ans = 3 3 2 1 2 3 4 5 u = 3 3 2 1 2 3 4 5 i = 4 ans = 4 4 ans = 4 4 3 ans = 4 4 3 2 ans = 4 4 3 2 1 ans = 4 4 3 2 1 2 ans = 4 4 3 2 1 2 3 ans = 4 4 3 2 1 2 3 4 u = 4 4 3 2 1 2 3 4 i = 5 ans = 5 5 ans = 5 5 4 ans = 5 5 4 3 ans = 5 5 4 3 2 ans = 5 5 4 3 2 2 ans = 5 5 4 3 2 2 3 ans = 5 5 4 3 2 2 3 4 u = 5 5 4 3 2 2 3 4 i = 6 ans = 6 6 ans = 6 6 5 ans = 6 6 5 4 ans = 6 6 5 4 3 ans = 6 6 5 4 3 3 ans = 6 6 5 4 3 3 2 ans = 6 6 5 4 3 3 2 3 ans = 3

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

ans = 0 1 2 3 4 5 6 u = 0 1 2 3 4 5 6 i = 1 ans = 1 0 ans = 1 0 1 ans = 1 0 1 2 ans = 1 0 1 2 3 ans = 1 0 1 2 3 4 ans = 1 0 1 2 3 4 5 u = 1 0 1 2 3 4 5 i = 2 ans = 2 1 ans = 2 1 1 ans = 2 1 1 2 ans = 2 1 1 2 3 ans = 2 1 1 2 3 3 ans = 2 1 1 2 3 3 4 u = 2 1 1 2 3 3 4 i = 3 ans = 3 2 ans = 3 2 2 ans = 3 2 2 2 ans = 3 2 2 2 3 ans = 3 2 2 2 3 4 ans = 3 2 2 2 3 4 4 u = 3 2 2 2 3 4 4 i = 4 ans = 4 3 ans = 4 3 2 ans = 4 3 2 3 ans = 4 3 2 3 3 ans = 4 3 2 3 3 4 ans = 4 3 2 3 3 4 5 u = 4 3 2 3 3 4 5 i = 5 ans = 5 4 ans = 5 4 3 ans = 5 4 3 3 ans = 5 4 3 3 4 ans = 5 4 3 3 4 4 ans = 5 4 3 3 4 4 5 u = 5 4 3 3 4 4 5 i = 6 ans = 6 5 ans = 6 5 4 ans = 6 5 4 4 ans = 6 5 4 4 3 ans = 6 5 4 4 3 4 ans = 6 5 4 4 3 4 5 u = 6 5 4 4 3 4 5 i = 7 ans = 7 6 ans = 7 6 5 ans = 7 6 5 5 ans = 7 6 5 5 4 ans = 7 6 5 5 4 3 ans = 7 6 5 5 4 3 4 u = 7 6 5 5 4 3 4 i = 8 ans = 8 7 ans = 8 7 6 ans = 8 7 6 6 ans = 8 7 6 6 5 ans = 8 7 6 6 5 4 ans = 8 7 6 6 5 4 3 ans = 3

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

ans = 0 1 2 3 4 5 6 7 8 9 u = 0 1 2 3 4 5 6 7 8 9 i = 1 ans = 1 0 ans = 1 0 1 ans = 1 0 1 2 ans = 1 0 1 2 3 ans = 1 0 1 2 3 4 ans = 1 0 1 2 3 4 5 ans = 1 0 1 2 3 4 5 6 ans = 1 0 1 2 3 4 5 6 7 ans = 1 0 1 2 3 4 5 6 7 8 u = 1 0 1 2 3 4 5 6 7 8 i = 2 ans = 2 1 ans = 2 1 1 ans = 2 1 1 2 ans = 2 1 1 2 3 ans = 2 1 1 2 3 4 ans = 2 1 1 2 3 4 5 ans = 2 1 1 2 3 4 5 6 ans = 2 1 1 2 3 4 5 6 7 ans = 2 1 1 2 3 4 5 6 7 8 u = 2 1 1 2 3 4 5 6 7 8 i = 3 ans = 3 2 ans = 3 2 2 ans = 3 2 2 2 ans = 3 2 2 2 3 ans = 3 2 2 2 3 4 ans = 3 2 2 2 3 4 5 ans = 3 2 2 2 3 4 5 6 ans = 3 2 2 2 3 4 5 6 7 ans = 3 2 2 2 3 4 5 6 7 8 u = 3 2 2 2 3 4 5 6 7 8 i = 4 ans = 4 3 ans = 4 3 3 ans = 4 3 3 3 ans = 4 3 3 3 3 ans = 4 3 3 3 3 4 ans = 4 3 3 3 3 4 5 ans = 4 3 3 3 3 4 5 6 ans = 4 3 3 3 3 4 5 6 7 ans = 4 3 3 3 3 4 5 6 7 8 u = 4 3 3 3 3 4 5 6 7 8 i = 5 ans = 5 4 ans = 5 4 4 ans = 5 4 4 4 ans = 5 4 4 4 4 ans = 5 4 4 4 4 4 ans = 5 4 4 4 4 4 5 ans = 5 4 4 4 4 4 5 6 ans = 5 4 4 4 4 4 5 6 7 ans = 5 4 4 4 4 4 5 6 7 8 u = 5 4 4 4 4 4 5 6 7 8 i = 6 ans = 6 5 ans = 6 5 5 ans = 6 5 5 5 ans = 6 5 5 5 5 ans = 6 5 5 5 5 5 ans = 6 5 5 5 5 5 5 ans = 6 5 5 5 5 5 5 6 ans = 6 5 5 5 5 5 5 6 7 ans = 6 5 5 5 5 5 5 6 7 8 u = 6 5 5 5 5 5 5 6 7 8 i = 7 ans = 7 6 ans = 7 6 6 ans = 7 6 6 6 ans = 7 6 6 6 6 ans = 7 6 6 6 6 6 ans = 7 6 6 6 6 6 6 ans = 7 6 6 6 6 6 6 6 ans = 7 6 6 6 6 6 6 6 7 ans = 7 6 6 6 6 6 6 6 7 8 u = 7 6 6 6 6 6 6 6 7 8 i = 8 ans = 8 7 ans = 8 7 7 ans = 8 7 7 7 ans = 8 7 7 7 7 ans = 8 7 7 7 7 7 ans = 8 7 7 7 7 7 7 ans = 8 7 7 7 7 7 7 6 ans = 8 7 7 7 7 7 7 6 7 ans = 8 7 7 7 7 7 7 6 7 8 u = 8 7 7 7 7 7 7 6 7 8 i = 9 ans = 9 8 ans = 9 8 8 ans = 9 8 8 8 ans = 9 8 8 8 8 ans = 9 8 8 8 8 8 ans = 9 8 8 8 8 8 7 ans = 9 8 8 8 8 8 7 7 ans = 9 8 8 8 8 8 7 7 7 ans = 9 8 8 8 8 8 7 7 7 8 u = 9 8 8 8 8 8 7 7 7 8 i = 10 ans = 10 9 ans = 10 9 9 ans = 10 9 9 9 ans = 10 9 9 9 9 ans = 10 9 9 9 9 9 ans = 10 9 9 9 9 9 8 ans = 10 9 9 9 9 9 8 8 ans = 10 9 9 9 9 9 8 8 8 ans = 10 9 9 9 9 9 8 8 8 8 u = 10 9 9 9 9 9 8 8 8 8 i = 11 ans = 11 10 ans = 11 10 10 ans = 11 10 10 10 ans = 11 10 10 10 10 ans = 11 10 10 10 10 10 ans = 11 10 10 10 10 10 9 ans = 11 10 10 10 10 10 9 9 ans = 11 10 10 10 10 10 9 9 8 ans = 11 10 10 10 10 10 9 9 8 9 u = 11 10 10 10 10 10 9 9 8 9 i = 12 ans = 12 11 ans = 12 11 11 ans = 12 11 11 11 ans = 12 11 11 11 11 ans = 12 11 11 11 11 11 ans = 12 11 11 11 11 11 10 ans = 12 11 11 11 11 11 10 10 ans = 12 11 11 11 11 11 10 10 9 ans = 12 11 11 11 11 11 10 10 9 8 u = 12 11 11 11 11 11 10 10 9 8 i = 13 ans = 13 12 ans = 13 12 12 ans = 13 12 12 12 ans = 13 12 12 12 12 ans = 13 12 12 12 12 12 ans = 13 12 12 12 12 12 11 ans = 13 12 12 12 12 12 11 11 ans = 13 12 12 12 12 12 11 11 10 ans = 13 12 12 12 12 12 11 11 10 9 ans = 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))

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

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

ans = Columns 1 through 16 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Columns 17 through 23 16 17 18 19 20 21 22 u = Columns 1 through 16 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Columns 17 through 23 16 17 18 19 20 21 22 i = 1 ans = 1 1 ans = 1 1 2 ans = 1 1 2 3 ans = 1 1 2 3 4 ans = 1 1 2 3 4 5 ans = 1 1 2 3 4 5 6 ans = 1 1 2 3 4 5 6 7 ans = 1 1 2 3 4 5 6 7 8 ans = 1 1 2 3 4 5 6 7 8 9 ans = 1 1 2 3 4 5 6 7 8 9 10 ans = 1 1 2 3 4 5 6 7 8 9 10 11 ans = 1 1 2 3 4 5 6 7 8 9 10 11 12 ans = 1 1 2 3 4 5 6 7 8 9 10 11 12 13 ans = 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ans = 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ans = Columns 1 through 16 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Column 17 16 ans = Columns 1 through 16 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Columns 17 through 18 16 17 ans = Columns 1 through 16 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Columns 17 through 19 16 17 18 ans = Columns 1 through 16 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Columns 17 through 20 16 17 18 19 ans = Columns 1 through 16 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Columns 17 through 21 16 17 18 19

Suggested Problems

More from this Author95

Community Treasure Hunt

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

Start Hunting!