44. Trie Implementation and Advanced Operations

Implement "TRIE” data structure from scratch with the following functions.

  • Trie(): Initialize the object of this “TRIE” data structure.
  • insert(“WORD”): Insert the string “WORD” into this “TRIE” data structure.
  • countWordsEqualTo(“WORD”): Return how many times this “WORD” is present in this “TRIE”.
  • countWordsStartingWith(“PREFIX”): Return how many words are there in this “TRIE” that have the string “PREFIX” as a prefix.
  • erase(“WORD”): Delete one occurrence of the string “WORD” from the “TRIE”.

Example 1:

Input : ["Trie", "insert", "countWordsEqualTo", "insert", "countWordsStartingWith", "erase", "countWordsStartingWith"]

[ "apple", "apple", "app", "app", "apple", "app" ]

Output : [null, null, 1, null, 2, null, 1]

Explanation :

Trie trie = new Trie()

trie.insert("apple")

trie.countWordsEqualTo("apple")  // return 1

trie.insert("app") 

trie.countWordsStartingWith("app") // return 2

trie.erase("apple")

trie.countWordsStartingWith("app")   // return 1

Example 2:

Input : ["Trie", "insert", "countWordsEqualTo", "insert", "erase", "countWordsStartingWith"]

[ "mango", "apple", "app", "app", "mango" ]

Output : [null, null, 0, null, null, 1]

Explanation :

Trie trie = new Trie()

trie.insert("mango")

trie.countWordsEqualTo("apple")  // return 0

trie.insert("app") 

trie.erase("app")

trie.countWordsStartingWith("mango") // return 1

Now Your Turn!

Pick the correct output for the given input

Input : ["Trie", "insert", "insert", "erase", "countWordsEqualTo", "insert", "countWordsStartingWith"]

["abcde","fghij","abcde", "bcde", "abcde", "fgh"]

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

  • 1 <= word.length , prefix.length <= 2000
  • word and prefix consist only of lowercase English letters.
  • At most 3*104 calls in total will be made to insert, countWordsEqualTo , countWordsStartingWith and erase.

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

0
class Trie {
public:
Trie() {
}
 
void insert(string word) {
}
 
int countWordsEqualTo(string word) {
}
 
int countWordsStartingWith(string word) {
}
 
void erase(string word) {
}
};
 
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* int param_2 = obj->countWordsEqualTo(word);
* int param_3 = obj->countWordsStartingWith(prefix);
* obj->erase(word);
*/
Test Case

Input:

Operations
Values
to save your code