2 ms·
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
by dominotw 7y ago
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
- Cpoll 7y agoI 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.
- dominotw 7y agoah yea, sorry i misread the question.
- senderista 7y agoThat only works up to permutations.