Problem 93. Calculate the Levenshtein distance between two strings
Solution Stats
Problem Comments
-
3 Comments
Good question
I really like this problem. So far, this is the one I had to think about most. Mostly because the straight-forward recursive implementation is simply not feasible for longer inputs.
This question is a good example of using a bottom-up dynamic programming algorithm.
Solution Comments
-
1 Comment
That was really interesting :)
-
1 Comment
Go back to school!
-
1 Comment
Shameless code... now i'll do that in right way.
-
1 Comment
The simplest solution for beginner, now I'm trying to solve in a correct way
-
3 Comments
Apparently the test suite needs to be augmented!
Done. People never get tired of look-up tables.
Indeed: all of the current supposedly 'top ten' submissions here (by Cody-size) are hard-coded hacks! The Test Suite can be augmented by: (i) adding more arbitrary test cases; (ii) adding test cases in which the first [and last] characters/words are the same as in some other test case(s); (iii) banning mention of numbers that correspond to results and need not be mentioned in legitimate submissions (e.g. 18, 25, 27) [as implemented for Problem 44466]; and (iv) potentially banning other key words appearing in other 'generic' hacks (per Solutions 312146 and 1039520). —DIV
Problem Recent Solvers944
Suggested Problems
-
16563 Solvers
-
692 Solvers
-
Flip the main diagonal of a matrix
619 Solvers
-
Calculate the area of a triangle between three points
2129 Solvers
-
Solving Quadratic Equations (Version 1)
468 Solvers
More from this Author96
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!