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.
O(k*log(n) + k^2*n) = O(k^2*n)
We're a place where coders share, stay up-to-date and grow their careers.
We strive for transparency and don't collect excess data.