Trie is an efficient information reTrieval data structure. Using Trie, search complexities can be brought to an optimal limit (key length). If we store keys in the binary search tree, a well-balanced BST will need time proportional to M * log N, where M is the maximum string length and N is the number of keys in the tree. Using Trie, we can search the key in O(M) time.
There are many questions in strings where we should use a trie data structure, instead of other algorithms. For example, if there is a word in the dictionary, which you need to search, whether it is present or not. The most basic approach, that will come to your mind is to search the word one by one in the dictionary.
But, if we are searching for the word "NO", and in the dictionary, we have {"Not", "Notes", "Notable", "Nope"}, then we will search character by character. Now, consider a word with 1 lakh length. If would become more complex and you will definitely get TLE, in CP.
So, what you can do is, make use of the TRIE data structure.
Here, what we are doing is, creating a class Node, where we have data, map, and terminal as its elements. We have an unordered map, which links the first character of the word, to all the words starting from it. For example, we have {"Apple", "Ants", "Animals", "Amphibians"}, then the map will link the character "A", with the tree which consisted of the rest of the letters as shown below.
Now, we will create another class TRIE, which will create our whole tree
Now we will create a function insert node, which will take the word as an argument, and will create the whole trie.
Here, we defined a temp Node, which contains the root node.
Now, we iterate through the characters in the word and will check, whether it is already present or not, if not, we create a new node and link it to our unordered_map.
After iterating through the whole character array, make sure to put temp->terminal to true, which will indicate that the word ends.
That's all for the TRIE data structure.
Happy Coding :)
Top comments (0)