Tries
Tries is a special kind of data structure which gives efficient time complexity for search operation
With tries, we can search a 'query string' of length 'n' in O(n) time
They are quite simple and straightforward to implement
The classic use case of tries include all applications which require efficient search time, for example: autocomplete, phone book directory, key look up etc
Most of the time, only possible downside to tries in a system can be large memory consumed while maintaining the tries owing to additional pointers. Although we can mimic the functionality of a trie and implement it using arrays
Tries are also self referential like many other data structures (which include Linked List, Trees, etc)
Tries data structure is a collection of nodes, where we have a root node as the starting node. Each node has some children, the maximum number of children a node can possess is bound by the size of the aphabet ( in most of the common implementations ). For English alphabet, this number is 26
some pseudo code:
# define SIZE 26
class node{
bool is_end_of_word=false;
node *children[SIZE]={0};
}
bool search(string s, node *root, int i=0){
if(i==s.length() && is_end_of_word)
return true;
if(i==s.length())
return false;
char c = s[i];
if(root->children[i])
return search(s, root->children[i], i+1)
else
return false;
}