Menu
I am reading about trie data structure and found two implementations to implement the children in trie node. Following are the details of the two implementations :-
1) Trie node array of length 26 has been used to store children of the trie node.
2) HashMap has been used to store children of the trie node with character as the key and Trie node as the value.
Please let me know which implementation is better and why?
362
One way to implementing Trie is linked set of nodes, where each node contains an array of child pointers, one for each symbol in the alphabet. This is not efficient in terms of time as we can't quickly find a particular child. The efficient way is an implementation where we use hash map to store children of a node.
In a trie indexing an alphabet of 26 letters, each node has 26 possible children and, therefore, 26 possible pointers.
Implement the Trie class: Trie() Initializes the trie object. void insert(String word) Inserts the string word into the trie. boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
It depends - a usual trade-off between memory and speed.
If your strings are short and you don't have memory issues then of course go for the array. This way you make your searches faster. Also good if your letters are evenly distributed among words.
If your strings can be large and there are some letters that occur very rarely then go for the hash map. This way you don't occupy too much unused memory. That's also better if your alphabet is much larger than 26 letters.
Array is faster but potentially consumes more memory than HashMap - but not necessary. Imagine that your bag of words contain all the possible 26^N words of length N that can be made of 26 letters. Then HashMap would be both slower and consume more memory.
67
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
