-1

I am working on one problem "Most frequent word in an array of strings" and got confused to understand which will be more efficient solution: a trie or a dictionary?

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
Ayushi Gupta
  • 173
  • 1
  • 2
  • 13

1 Answers1

2

A dictionary is sufficient.

A trie is useful if you're searching for word prefixes, like you want all words that start with "ca": "car", "cat", etc. It won't help if you're not doing something prefix-related.

John Kugelman
  • 349,597
  • 67
  • 533
  • 578
  • Is there any performance cost associated if we have more elements in array in case of dictionary ? I was referring to the following article which uses hashing and min heap approach for the same: "https://stackoverflow.com/questions/185697/the-most-efficient-way-to-find-top-k-frequent-words-in-a-big-word-sequence"? – Ayushi Gupta Nov 02 '19 at 11:29
  • If the dictionary is a hash table then adding and searching are amortized constant time operations: that means fast. If you need help writing the program I recommend you give it a shot and then post another question with your code. – John Kugelman Nov 02 '19 at 11:35
  • Printing the *k* most frequent words is more complicated than printing the single most frequent word and benefits from a more sophisticated algorithm / data structure. – John Kugelman Nov 02 '19 at 11:37