This problem description is lifted from http://en.wikipedia.org/wiki/Levenshtein_distance.
The Levenshtein distance between two strings is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character.
For example, the Levenshtein distance between "kitten" and "sitting" is 3, since the following three edits change one into the other, and there is no way to do it with fewer than three edits:
kitten => sitten (substitution of 's' for 'k') sitten => sittin (substitution of 'e' for 'i') sittin => sitting (insert 'g' at the end).
So when
s1 = 'kitten'
and
s2 = 'sitting'
then the distance d is equal to 3.
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.
Shameless code... now i'll do that in right way.
The simplest solution for beginner, now I'm trying to solve in a correct way
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
Make an N-dimensional Multiplication Table
106 Solvers
267 Solvers
Find perfect placement of non-rotating dominoes (easier)
232 Solvers
Find the dimensions of a matrix
273 Solvers
Pernicious Anniversary Problem
684 Solvers