Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Tries Interview Questions

Find words

Harsh

Last Updated on March 28, 2022 by Ria Pathak

Concepts Used

Trie

Difficulty Level

Easy

Problem Statement :

Given a blank dictionary. Now in the first set of operations, you have to insert N integers in the dictionary. And then you have to find M words in the dictionary and print "Present" if the word is present and "Not" if the word is not present in the Dictionary.

See original problem statement here

Solution Approach :

Introduction :

We will generate a tree with 26 outgoing nodes, for every alphabet. Insert every character as an individual node of the tree and mark where every word ends. This marking of word end will help us search a given word.

Description:

We will use trie to solve this problem.
A Trie is a special data structure used to store strings that can be visualized like a graph. It consists of nodes and edges. Each node consists of atmost 26 children and edges connect each parent node to its children. These 26 node pointers is for 26 letters of the English alphabet. A separate edge is maintained for every edge.
We will insert every character of the word as individual node and now that we already know (from the definition above) that every node is a pointer to 26 different nodes which represents alphabets, we will determine if the input character is new or an extension of the previously inserted character. If it is new we will create a node and add it to the tree, otherwise we will keep inserting the character(node) , then mark the last character of the word being inserted, as the word end.
Now that we have inserted our words into the tree we will we given few other words whether they are present in the tree or not. We will search for every character , left to right, of the word (value to be searched). If every character is present and the last node of the tree (trie) which matches the last character of the word 9being searched) is the word end, then we can say its "Present" otherwise it is not.

Algorithm :

insert():

  • iterate for every character in string, value,
  • check if the character previously being inserted,
  • if not, make a new tree node for this character and add it as the children of the root.
  • if it is already present, make the child node as parent and do the same with the remaining characters in value.
  • After inserting the last character node of value in tree , mark that node as word end.

search():

  • iterate for every character c in string, key,
  • if c is not present, childern[c]==NULL, return FALSE.
  • else, if all c are present and the current node is not NULL and current node is the word end, return TRUE.

Complexity Analysis :

We are inserting the characters of length M, lets say. Also we are searching for M character array at a time for a single query.

Space complexity of this data structure would be O(26*M*N), where M is the length of the string , N is the number of nodes in trie.

Solutions:

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <stdbool.h> 

#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0]) 

#define ALPHABET_SIZE (26) 

#define CHAR_TO_INDEX(c) ((int)c - (int)'a') 

struct TrieNode 
{ 
    struct TrieNode *children[ALPHABET_SIZE]; 

    // isEndOfWord is true if the node represents 
    // end of a word 
    bool isEndOfWord; 
}; 

struct TrieNode *getNode(void) 
{ 
    struct TrieNode *pNode = NULL; 

    pNode = (struct TrieNode *)malloc(sizeof(struct TrieNode)); 

    if (pNode) 
    { 
        int i; 

        pNode->isEndOfWord = 0; 

        for (i = 0; i < ALPHABET_SIZE; i++) 
            pNode->children[i] = NULL; 
    } 

    return pNode; 
} 

void insert(struct TrieNode *root, const char *key) 
{ 
    int level; 
    int length = strlen(key); 
    int index; 

    struct TrieNode *pCrawl = root; 

    for (level = 0; level < length; level++) 
    { 
        index = CHAR_TO_INDEX(key[level]); 
        if (!pCrawl->children[index]) 
            pCrawl->children[index] = getNode(); 

        pCrawl = pCrawl->children[index]; 
    } 

    // mark last node as leaf 
    pCrawl->isEndOfWord = true; 
} 


int search(struct TrieNode *root, const char *key) 
{ 
    int level; 
    int length = strlen(key); 
    int index; 
    struct TrieNode *pCrawl = root; 

    for (level = 0; level < length; level++) 
    { 
        index = CHAR_TO_INDEX(key[level]); 

        if (!pCrawl->children[index]) 
            return false; 

        pCrawl = pCrawl->children[index]; 
    } 

    return (pCrawl != NULL && pCrawl->isEndOfWord); 
} 

int main() 
{ 
    int t;
    scanf("%d",&t);
    while(t--)
    {
      int n,m;
      scanf("%d %d", &n,&m);
      struct TrieNode *root = getNode(); 
      char *key = (char *)malloc(sizeof(char)*1001);
      char *val = (char *)malloc(sizeof(char)*1001);;

      for(int i=0;i<n;i++)
      {
        scanf("%s",key);
        insert(root, key); 
      }

      for(int i=0;i<m;i++)
      {
        scanf("%s",val);
        search(root,val)?printf("%s\n","Present"):printf("%s\n","Not");
      }
    }

    return 0; 
} 

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

const int ALPHABET_SIZE = 26; 

// trie node 
struct TrieNode 
{ 
    struct TrieNode *children[ALPHABET_SIZE]; 
    bool isEndOfWord; 
}; 

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]; 
    } 

    pCrawl->isEndOfWord = true; 
} 

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); 
} 


int main()
    { 
        int t;
        cin>>t;
        while(t--)
        {
          int n,m;
          cin>>n>>m;
          string keys[n],find[m];

          struct TrieNode *root = getNode(); 


          for(int i=0;i<n;i++)
           {
             cin>>keys[i];
             insert(root, keys[i]); 
           }

         for(int i=0;i<m;i++)

          {
            cin>>find[i];
                // Search for different keys 
         search(root, find[i])? cout << "Present\n":cout << "Not\n"; 
          }


        }
    return 0; 
} 

import java.util.*;

public class Main { 

    static final int ALPHABET_SIZE = 26; 

    static class TrieNode 
    { 
        TrieNode[] children = new TrieNode[ALPHABET_SIZE]; 

        boolean isEndOfWord; 

        TrieNode(){ 
            isEndOfWord = false; 
            for (int i = 0; i < ALPHABET_SIZE; i++) 
                children[i] = null; 
        } 
    }; 

    static TrieNode root; 

    static void insert(String key) 
    { 
        int level; 
        int length = key.length(); 
        int index; 

        TrieNode pCrawl = root; 

        for (level = 0; level < length; level++) 
        { 
            index = key.charAt(level) - 'a'; 
            if (pCrawl.children[index] == null) 
                pCrawl.children[index] = new TrieNode(); 

            pCrawl = pCrawl.children[index]; 
        } 

        // mark last node as leaf 
        pCrawl.isEndOfWord = true; 
    } 

    // Returns true if key presents in trie, else false 
    static boolean search(String key) 
    { 
        int level; 
        int length = key.length(); 
        int index; 
        TrieNode pCrawl = root; 

        for (level = 0; level < length; level++) 
        { 
            index = key.charAt(level) - 'a'; 

            if (pCrawl.children[index] == null) 
                return false; 

            pCrawl = pCrawl.children[index]; 
        } 

        return (pCrawl != null && pCrawl.isEndOfWord); 
    } 

    public static void main(String args[]) 
    { 
     Scanner sc = new Scanner(System.in);
     int t= sc.nextInt();
     while(t-->0)
     {
        String key,val;

        root = new TrieNode(); 
        int n= sc.nextInt();
        int m = sc.nextInt();

        for (int i = 0; i < n; i++) 
        {
          key = sc.next();
            insert(key); 
        }

        for(int j=0;j<m;j++)
        {
          val = sc.next();
          if(search(val) == true) 
              System.out.println("Present"); 
          else System.out.println("Not"); 
        }

     }

    } 
} 

# your code goes here
ALPHABET_SIZE = 26
class TrieNode:
	def __init__(self):
		self.children = [None]*ALPHABET_SIZE
		self.isEndOfWord = None

def getNode():
	pNode = TrieNode()
	pNode.isEndOfWord = False
	return pNode

def insert(root, key):

	pCrawl = root
	
	for i in range(len(key)):
	
		index = ord(key[i]) - ord("a")
	
		if not pCrawl.children[index]:
	
			pCrawl.children[index] = getNode()
	
		pCrawl = pCrawl.children[index]
	
	pCrawl.isEndOfWord = True

def search(root, key):
	pCrawl = root
	for i in range(len(key)):
		index = ord(key[i]) - ord("a")
		if not pCrawl.children[index]:
			return False
		pCrawl = pCrawl.children[index]
	return pCrawl and pCrawl.isEndOfWord

for _ in range(int(input())):
	n, m = map(int,input().split())
	keys = input().split()
	find = input().split()
	root = getNode()
	for i in range(n):
		insert(root, keys[i])

	for i in range(m):
		res = search(root, find[i])
		if res:
			print("Present")
		else:
			print("Not")

[forminator_quiz id="2263"]

This article tried to discuss Trie. Hope this blog helps you understand and solve the problem. To practice more problems on Trie you can check out MYCODE | Competitive Programming.

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post