Re:The Lesson to Unlearn
by Cpoll on Saturday December 07, 2019 @09:01PM
(#21733934)
I might be misunderstanding, but doesn't that treat 'abc' and 'cba' as distance 0?
Regardless, I was also thinking Levenshtein is sub-optimal, and that you can probably solve it in O(n+m).
Even if you go for Levenshtein first, you should identify a simple modification to stop calculating the matrix early if the distance is necessarily greater than 1. Get a bit fancier and you can just 'go down the diagonal' and greatly optimize the algorithm.
Regardless, I was also thinking Levenshtein is sub-optimal, and that you can probably solve it in O(n+m).
Even if you go for Levenshtein first, you should identify a simple modification to stop calculating the matrix early if the distance is necessarily greater than 1. Get a bit fancier and you can just 'go down the diagonal' and greatly optimize the algorithm.