458. Implement Trie II (Prefix Tree)

You need to design a Trie (prefix tree) with enhanced functionalities. Implement the class Trie that supports the following operations:

  • void insert(string word) : Inserts the word into the Trie.
  • int countWordsEqualTo(string word): Returns the number of times word was inserted into the Trie.
  • int countWordsStartingWith(string prefix): Returns the number of words in the Trie that start with the given prefix.
  • void erase(string word): Removes the word from the Trie. It is guaranteed that the word exists in the Trie before calling this function.

Example 1:

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

values : [[], ["apple"], ["apple"], ["app"], ["apple"], ["app"], ["apple"], ["apple"], ["app"]]

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

Explanation :

Insert "apple" twice and "app" once.

"apple" appears twice, "app" appears once, and prefix "app" appears in "apple" and "app" (total 3).

Erase "apple" once. Now, "apple" appears once, "app" prefix count is 2.

Example 2:

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

values : [[], ["apple"], ["apple"], ["apple"], ["app"], ["apple"], ["apple"], ["app"], ["apple"], ["app"]]

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

Explanation :

Insert "banana", "band", then query prefix "ban" → count = 2 ("banana", "band").

Erase "banana", now "banana" count is 0, prefix "ban" count is 1 ("band" remains).

Now Your Turn!

Pick the correct output for the given input

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

values : [[], ["dog"], ["door"], ["dear"], ["dog"], ["do"], ["dog"], ["dog"], ["do"], ["door"], ["door"], ["do"]]

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 * 10⁴ calls in total will be made to insert, countWordsEqualTo, countWordsStartingWith, and erase.
  • It is guaranteed that for any function call to erase, the string word will exist in the trie.

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