Last Updated: 6 Apr, 2021

Implement Trie ll

Moderate

Asked in companies

Solve now

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?

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.

Solve now

Approaches

01 Approach

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:

Declare a global variable “root” denotes the root of our “TRIE” data structure.
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”.
trie():
- Make an object of struct/class “TrieNode” and store it in “root”.
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.
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”.
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”.
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".

Solve now