How to sort an array of strings with anagrams next to each other

Question

How to sort an array of strings with anagrams next to each other?

Eg:

input {god, dog, abc, cab, man}
output {abc, cab, dog, god, man}

My approach: Sort the array ( without considering the anagrams case) in O(nlogn). Next, pick up the first string & create a histogram for the string, and compare the histogram with the remaining strings histograms in the array and place the matching strings at appropriate position of the array ..repeat until it reaches array size.. this algo takes worst case of O(n^3) (if we assume that in worst case, each string is also of size n) & extra space for the histogram representation

Histogram approach taken from the ref: finding if two words are anagrams of each other

Can we do better than this?

Answer 1

You can certainly do better as follows:

1. Loop through the array of strings
2. For each string, first sort its characters, using the sorted string as key and original string as value, put into a hash table. you will end up with a hash table that with keys as sorted strings, and values being all anagrams, meanwhile, those values are ordered. You may use map<string, set<string> > to serve for this purpose.
3. iterate over the hash-table and output all anagrams together for a given key, they should be next to each other

Assume the length of strings are M and size of array is N the time complexity is then: O(NMlogM), M is usually smaller than N in average. So this is much more efficient than what you have said.