2

Given array of words, group the anagrams IP:{tar,rat,banana,atr} OP:{[tar,rat,atr],[banana]}

One solution to this question using Hash Table. consider each word, sort it and add as key to hash table if not present. The value for the key would be a list of all anagrams with the same key. I wanted to know about the time complexities, To sort the characters in an array, suppose O(n log n) To store in the hash table it would be O(n), a total of O(n*nlogn).

Is there a better algorithm? with lesser time complexity?

user2626431
  • 447
  • 1
  • 10
  • 20
  • But `n` is the length of a word, not the number of words in your array, so it shouldn't be too bad. Regardless, you could define your own hash function that would be independent of rearrangements. For example, add up the letter values: tar -> 20+1+18=39. But that may not be a very good hash. – Teepeemm Jul 29 '13 at 21:41
  • I can't see the relationship between this question and the dup. See [here](http://stackoverflow.com/a/18144931/2417578) for an order-agnostic hash. The test app I wrote dumped hashes and words and I sorted that by hash to group anagrams together, which seems to be the way you're headed. – sh1 Aug 10 '13 at 00:49

1 Answers1

1

For time complexity's sake, you could always use counting sort to sort the individual words, which cost just linear time per word. You can also first count the occurrences of letters then hash the occurrences count instead of the sorted word, which is essentially the same as counting sort minus the rebuild step.

But since the words will typically be short, this might not buy you any practical advantages.

zw324
  • 26,764
  • 16
  • 85
  • 118
  • +1. in term of big O notation, the solution to count the frequency of letters and then hashing it, surely is better than O(N* M * lg(M)) where M is the length of the longest string. Because according to your solution, it has O(26*N*M) = O(N*M). But I agree with you that it won't buy any practical advantage (even as N and M are small, it might perform worse than what OP is doing now) :) – Fallen Jul 29 '13 at 22:08
  • Well, this was an interview question and I had coded the answer that I described in my question. But I dint clear the interview. So wanted to know if something better exists. – user2626431 Jul 29 '13 at 23:27
  • There are too many factors for an interview, e.g., how good is the program you wrote? Did you gave a good analysis? Were you a good cultural match? But algorithmic wise, the answer you given should be enough. – zw324 Jul 29 '13 at 23:42
  • Well, I had one small bug which I ended correcting after he asked to review my code. Kicking myself for that literally. Pretty sure everything else was good. – user2626431 Jul 29 '13 at 23:54