News for hackers. Stuff that matters.

A comment on The Lesson to Unlearn. Parent comment

Re:The Lesson to Unlearn by dominotw on Saturday December 07, 2019 @08:41PM (#21733869)
1st for loop with first word with charecter counts map and second for loop subtracting counts from frist map. See whats remaining in the end, either a map with 1 char left or 1 char left in second. so O(m + n).

abc , adc

a - 1

b - 1

c - 1

after second word loop

b - 1, d

[ Parent | on HN ]
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.

[ Parent | on HN ]
Re:The Lesson to Unlearn by dominotw on Saturday December 07, 2019 @09:04PM (#21733940)
ah yea, sorry i misread the question.
[ Parent | on HN ]
Re:The Lesson to Unlearn by senderista on Sunday December 08, 2019 @12:26AM (#21734474)
That only works up to permutations.
[ Parent | on HN ]