DEV Community

loading...

Discussion on: Advent of code Day 2 Part 2 Complexity

Collapse
conectado profile image
Conectado Author

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.

Collapse
stevemoon profile image
Steve Moon

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.

Thread Thread
conectado profile image
Conectado Author

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.