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.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
What you're looking for is a Levenshtein distance of 1. Most languages will have a library function for calculating the Levenshtein distance.
en.wikipedia.org/wiki/Levenshtein_...
Or go all hardcore algorithm on it and re-implement it yourself if that's your thing...
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 takingO(k*n)k times and since we can assumek<<nthis solves the problem. Brilliant! I will implement this ASAP.