Implement Trie ll

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
231 upvotes
Asked in companies
FlipkartUberAmazon

Problem statement

Ninja has to implement a data structure ”TRIE” from scratch. Ninja has to complete some functions.

1) Trie(): Ninja has to initialize the object of this “TRIE” data structure.

2) insert(“WORD”): Ninja has to insert the string “WORD”  into this “TRIE” data structure.

3) countWordsEqualTo(“WORD”): Ninja has to return how many times this “WORD” is present in this “TRIE”.

4) countWordsStartingWith(“PREFIX”): Ninjas have to return how many words are there in this “TRIE” that have the string “PREFIX” as a prefix.

5) erase(“WORD”): Ninja has to delete one occurrence of the string “WORD” from the “TRIE”.

Note:

1. If erase(“WORD”) function is called then it is guaranteed that the “WORD” is present in the “TRIE”.

2. If you are going to use variables with dynamic memory allocation then you need to release the memory associated with them at the end of your solution.

Can you help Ninja implement the "TRIE" data structure?

Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line contains a single integer “T” representing the number of test cases. 

The first line of each test case will contain a single integer “N” which denotes how many times the functions(as discussed above) will be called.

The next “N” lines contain the two space-separated strings, the first one is the name of the function and the second one is a “WORD”.
Output Format:
For each test case, complete all the functions as we discussed above.

The output for every test case will be printed in a separate line.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= “T” <= 50
1 <= “N” <= 10000
 “WORD” = {a to z}
1 <= | “WORD” | <= 1000

Where “T” is the number of test cases, “N” denotes how many times the functions(as discussed above) we call, “WORD” denotes the string on which we have to perform all the operations as we discussed above, and | “WORD” | denotes the length of the string “WORD”.

Time limit: 1 sec.
Sample Input 1:
1
5
insert coding
insert ninja
countWordsEqualTo coding
countWordsStartingWith nin
erase coding
Sample Output 1:
1
1   
Explanation of sample input 1:
After insertion of “coding” in “TRIE”:

After insertion of “ninja” in “TRIE”:

Count words equal to “coding” :

Count words those prefix is “nin”:

After deletion of the word “coding”, “TRIE” is:

Sample Input 2:
1
6
insert samsung
insert samsung
insert vivo
erase vivo
countWordsEqualTo samsung
countWordsStartingWith vi
Sample Output 2:
2
0
Explanation for sample input 2:
insert “samsung”: we are going to insert the word “samsung” into the “TRIE”.

insert “samsung”: we are going to insert another “samsung” word into the “TRIE”.

insert “vivo”: we are going to insert the word “vivo” into the “TRIE”.

erase “vivo”: we are going to delete the word “vivo” from the “TRIE”.

countWordsEqualTo “samsung”: There are two instances of “sumsung” is present in “TRIE”.

countWordsStartingWith “vi”: There is not a single word in the “TRIE” that starts from the prefix “vi”.
Hint

Can you think of a brute force approach?

Approaches (1)
Brute Force

First, we declare a “TRIE” class/struct. In this “TRIE” class/struct there are three fields.

  • TrieNode children[26].
  • wordCount.
  • prefixCount.

 

insert(“WORD”) function:

In this function, we add this ‘WORD” into this “TRIE” data structure.

 

countWordsEqualTo(“WORD”) function:

In this function, we count how many times this word is present in this “TRIE”.

 

countWordsStartingWith(“PREFIX”) function:

In this function, we count how many words are present in this “TRIE” those having prefix is equal to "PREFIX".

 

erase("WORD") function:

In this function, we remove this word from “TRIE”.


 

Reference: https://www.codingninjas.com/blog/2020/09/22/using-trie-in-data-structures/

 

The steps are as follows:

 

  1. Declare a global variable “root” denotes the root of our “TRIE” data structure.
  2. struct/class TrieNode:
    • Make a “children” array/list of “TrieNode”  types.
    • Declare two variables “wordCount” and “prefixCount” in which we store the number of words that are equal to the given “WORD”, the number of words that prefix is equal to “PREFIX”.
  3. trie():
    • Make an object of struct/class “TrieNode” and store it in “root”.
  4. insert(“WORD”):
    • Create a new node “curr” of “TRIE” and initialize it with the “root” node of “TRIE”.
    • Run a for loop from ‘i’ = 0 to the length of the “WORD”:
      • “index” = ‘WORD[i]’ - ‘a’.
      • If “curr.children[“index”]” is equal to ”NULL”:
        • Add a new “TrieNode” node at this“curr” node.
      • “curr” is equal to “curr.children[“index”].
      • “curr.prefixCount” is equal to curr.prefixCount” plus 1.
    • “curr.wordCount” is equal to “curr.wordCount” plus 1.
  5. countWordsEqualTo(“WORD”):
    • Create a new node “curr” of “TRIE” and initialize it with the “root” node of “TRIE”.
    • Run a for loop from ‘i’ = 0 to the length of the “WORD”:
      • “index” = ‘WORD[i]’ - ‘a’.
      • If “curr.children[“index”]” is equal to ”NULL”:
        • Return 0.
      • “curr” is equal to “curr.children[“index”].
    • Finally, return “curr.wordCount”.
  6. countWordsStartingWith(“PREFIX”):
    • Create a new node “curr” of “TRIE” and initialize it with the “root” node of “TRIE”.
    • Run a for loop from ‘i’ = 0 to the length of the “WORD”:
      • “index” = ‘WORD[i]’ - ‘a’.
      • If “curr.children[“index”]” is equal to ”NULL”:
        • Return 0.
      • “curr” is equal to “curr.children[“index”].
    • Finally, return “curr.prefixCount”.
  7. erase(“WORD”):
    • Create a new node “curr” of “TRIE” and initialize it with the “root” node of “TRIE”.
    • Create a "toBeDeleted" node.
    • Run a for loop for ‘i’ = 0 to the length of the “WORD”:
      • “index” = ‘WORD[i]’ - ‘a’.
      • Create a "parent" node in which we store the parent of the current node and initialize it with "curr".
      • “curr” is equal to “curr.children[“index”].
      • “curr.prefixCount” is equal to curr.prefixCount” minus 1.
      • If "toBeDeleted"  is not equal to ”NULL”:
        • "toBeDeleted" is equal to "NULL".
      • If "curr.prefixCount"  is equal to 0:
        • If "toBeDeleted" is not equal to "NULL":
          • "parent.children[“index”]" is equal to "NULL".
          • "toBeDeleted" is equal to "curr".
        • "curr.wordCount” is equal to "curr.wordCount” minus 1.
    • If "toBeDeleted"  is not equal to ”NULL”:
      • "toBeDeleted" is equal to "NULL".
Time Complexity

For the insert function:

 

O(N), where ‘N’ is the number of words.

Because in the worst case when “TRIE’ is empty then we traverse the whole length of the word and insert every character in “TRIE”.


 

For the countWordsEqualTO function:

 

O(N), where ‘N’ is the number of words.

Because when we reach the end of the word then only we know how many times this word is present in the “TRIE”.


 

For countWordsStartingWith function:

 

O(N), where ‘N’ is the number of words.

Because in the worst case if the given prefix is the complete word that is present in the “TRIE” then we have to traverse the whole word in the “TRIE”.

 

 

For the erase function:

 

O(N), where ‘N’ is the number of words.

Because in the worst case only one word is present in the “TRIE” and we want to delete the complete word then we have to traverse the word from start to the end of this word.

Space Complexity

O(N * L), where ‘N’ and ‘L’ are the numbers of words and the length of the word.

 

Because we insert all the words in the “TRIE” and each character of a word contains 26 (constant) lengths array/vector.

Code Solution
(100% EXP penalty)
Implement Trie ll
Full screen
Console