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 code. The idea is to initialize
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 since the
Read more

Bit Manipulation Problems

We may face many Interview Questions which can ask us to find the Sum of XOR of all pairs of the array OR  Sum of XOR of all subsets   Generally, the constraints for these questions are very high with the value of each array element to be as large as 10^18. So that is a catch to use Bit manipulation method to solve the questions. We will be discussing some of these questions in this post.   Question  1:  Sum of XOR of all possible subsets   Given an array arr[] of size n, we need to find sum of all the values that comes from XORing all   the elements of the subsets.   Input                                                Output  3                                                       28  1 5 6   Explanation:  The most important clue for solving these questions is to find a pattern  with respect to the                property of XOR .  1 = 001 5 = 101 6 = 110 1 ^ 5 = 100 1 ^ 6 = 111 5 ^ 6 = 011 1^5^6 = 010 Total number of subs
Read more