re: Advent of code Day 2 Part 2 Complexity VIEW POST

TOP OF THREAD FULL DISCUSSION
re: What you're looking for is a Levenshtein distance of 1. Most languages will have a library function for calculating the Levenshtein distance. en.w...
 

Correct me if I'm wrong. But this distance is measured between 2 strings, and we have n strings in this case. Also, none of the algorithms presented in that article are better than linear in the size of the string so I don't think this is the solution to improve complexity.

 

Sort the list of strings and loop through comparing current and next string levenshtein distance. This works for this puzzle.

However, if the one-off strings don't happen to line up next to each other in sort order you'd want to build an index where the contents of the string are sorted, then sort the input based on the index. For example input string "zdfg" would have a sorted index of "dfgz". Then do the loop as above.

This is a great idea, if I understood correctly this solution could be implemented as O(k*log(n) + k^2*n) = O(k^2*n) basically you have to do one sort for each index(meaning at most k being the length of the words) and each of those k times you can compare each of the strings with its next string, that taking O(k*n) k times and since we can assume k<<n this solves the problem. Brilliant! I will implement this ASAP.

code of conduct - report abuse