The Trie Data Structure

Trie is an efficient information reTrieval data structure.

 Let word be a single string and let dictionary be a large set of words. If we have a dictionary, and we need to know if a single word is inside of the dictionary the tries are a data structure that can help us. 

 The following figure shows a trie with the words “tree”, “trie”, “algo”, “assoc”, “all”, and “also.”


The tries can insert and find strings in O(L) time (where L represent the length of a single word). 
Every node of Trie consists of multiple branches. Each branch represents a possible character of keys. We need to mark the last node of every key as end of word node.

 Structure of each node of a trie:-

 
// Trie node
struct TrieNode
{
     struct TrieNode *children[ALPHABET_SIZE];
     bool isEndOfWord;                       // represent end of word
};

 

struct TrieNode *getNode(void)
{
    struct TrieNode *pNode =  new TrieNode;
 
    pNode->isEndOfWord = false;
 
    for (int i = 0; i < ALPHABET_SIZE; i++)
        pNode->children[i] = NULL;
 
    return pNode;
}

 Operations(Templates):-

 Insert:

void insert(struct TrieNode *root, string key)
{
    struct TrieNode *pCrawl = root;
 
    for (int i = 0; i < key.length(); i++)
    {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            pCrawl->children[index] = getNode();
 
        pCrawl = pCrawl->children[index];
    }
 
    // mark last node as leaf
    pCrawl->isEndOfWord = true;
}
Search:

bool search(struct TrieNode *root, string key)
{
    struct TrieNode *pCrawl = root;
 
    for (int i = 0; i < key.length(); i++)
    {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            return false;
 
        pCrawl = pCrawl->children[index];
    }
 
    return (pCrawl != NULL && pCrawl->isEndOfWord);
}

 Doubts ?

  Reference Links:


 Lets Jump to some questions :
 Question 1: Link To Question

  If auto - completions exists, output all of them in lexicographical order(lowercase) else output "No  suggestions" without quotes.

  Input                                      Output

  3 fact
fact factorial
factorial factory
factory No suggestions
2
fact
pradyumn 

Solution: 


#include <bits/stdc++.h>
using namespace std;

const int ALPHABET_SIZE = 26;

struct TrieNode
{
     struct TrieNode *children[ALPHABET_SIZE];
     bool isEndOfWord;                       // represent end of word
};
 
struct TrieNode *getNode(void)
{
    struct TrieNode *pNode =  new TrieNode;
    pNode->isEndOfWord = false;
    for (int i = 0; i < ALPHABET_SIZE; i++)
        pNode->children[i] = NULL;
    return pNode;
}
 
void insert(struct TrieNode *root, string key)
{
    struct TrieNode *pCrawl = root;
 
    for (int i = 0; i < key.length(); i++)
    {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            pCrawl->children[index] = getNode();
 
        pCrawl = pCrawl->children[index];
    }
 
    // mark last node as leaf
    pCrawl->isEndOfWord = true;
}
 
struct TrieNode *search(struct TrieNode *root, string key)
{
    struct TrieNode *pCrawl = root;
    for (int i = 0; i < key.length(); i++)
    {
        int index = key[i] - 'a';
        if (!pCrawl->children[index])
            return NULL;
        pCrawl = pCrawl->children[index];
    }
    return pCrawl;
}

void dfs(struct TrieNode *curNode, string curString, vector<string> &res)
{
 for(int letter = 0; letter < ALPHABET_SIZE; letter++)
 {
  if(curNode->children[letter] != NULL)
  {
   string tmp = curString;
   tmp.push_back(letter + 'a');
   dfs(curNode->children[letter], tmp, res); 
  }
 }
 
 if(curNode->isEndOfWord)
  res.push_back(curString);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
 struct TrieNode *root= getNode();
 int n,q;
 cin>>n;
 while(n--)
 {
  string s;
  cin>>s;
  transform(s.begin(), s.end(), s.begin(), ::tolower);
  insert(root,s);
 }
 
 cin>>q;
 while(q--)
 {
  string s;
  cin>>s; 
  struct TrieNode *p = search(root,s);
  if(p==NULL)
  {
   cout <<"No suggestions\n"; 
   insert(root,s);
  }
  else
  {
   vector<string> res;
   dfs(p, s, res);
   sort(res.begin(), res.end());
   for(int i = 0, L = res.size(); i < L; i++)
    cout<<res[i]<<endl;
  }
 }
 
 return 0;
}


Practice Problems:








Comments

Post a Comment

Popular posts from this blog

Lazy Propagation - Too lazy to update all at a time

Image
Sometimes problems will ask you to update an interval from  l to r , instead of a single element. One solution is to update all the elements one by one. Complexity of this approach will be  O(N)  per operation since where are  N  elements in the array and updating a single element will take  O(logN)  time. To avoid multiple call to update function, we can modify the update function to work on an interval. For example consider the node with value 27 in above diagram, this node stores sum of values at indexes from 3 to 5. If our update query is for range 2 to 5, then we need to update this node and all descendants of this node. With Lazy propagation, we update only node with value 27 and postpone updates to its children by storing this update information in separate nodes called lazy nodes or values. We create an array lazy[] which represents lazy node. Size of lazy[] is same as array that represents segment tree, which is tree[] in below cod...
Read more

Combinatorial Game Theory

Image
Sometimes we find questions where two Players say A and B play a game optimally and we have to find out who ultimately is going to win the game provided there are some constraints. These questions are generally branched under the topic Combinatorial Game Theory. And the speciality about these is that the coding part is relatively very small and easy. The key to the Game Theory problems is the hidden observations which can be sometimes very hard to find. First, we will look at the basic division of positions to winning and losing . Question:  Two players are playing a game with n stones where player 1 always plays first. The two players move in alternating turns and play optimally. In a single move, a player can remove either 1, 3 or 4 stones from the pile of stones. If a player is unable to make a move then that player loses the game. Given the number of stones, find and print the name of the winner. Approach:  As we can see positions 1, 3 and 4 are winning positions ...
Read more

XOR Problems using Trie

Image
A Trie because of its re Trie Val property can be used to solve many problems that require to find the maximum XOR values or problems involving XOR. In this post, we will discuss similar problems where Trie can be used to solve them. Reference Links: Tutorials on Trie   Lets Jump to some questions  : Question  1:   MAX_XOR Given an array of integers , we have to find two elements whose XOR is maximum. Explanation: We First insert our numbers as bits in the Trie as we go. Now for finding the max XOR we start from the MSB and check along.  Let's say our number Y is b1,b2...bn, where b1,b2.. are binary bits. We start from b1. Now for the XOR to be maximum, we'll try to make most significant bit 1 after taking XOR. So, if b1 is 0, we'll need a 1 and vice versa. In the trie, we go to the required bit side. If favorable option is not there, we'll go other side. Doing this all over for i=1 to n, we'll get the maximum XOR possible. ...
Read more