Problem Statement

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”.

Examples

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