120. Count Prefix Using Trie

Count Prefix Using Trie

Implement a Trie (Prefix Tree) that supports inserting words and counting how many inserted words start with a given prefix.

The Trie must support only the following operations:
insert(word)
countWordsStartingWith(prefix)

If the same word is inserted multiple times, each insertion must be counted separately.

The method countWordsStartingWith(prefix) must return the total number of inserted words whose prefix matches the given prefix.

Methods

Trie()

Initializes an empty Trie.

void insert(String word)

1 ≤ word.length() ≤ 2000
word consists of lowercase english letters only.
Inserts word into the Trie.
If the same word is inserted multiple times, each insertion is stored and counted.

int countWordsStartingWith(String prefix)

1 ≤ prefix.length() ≤ 2000
prefix consists of lowercase English letters only.
Returns the number of inserted words that start with prefix.
Multiple insertions of the same word must be counted multiple times.

Constraints

1 ≤ total number of method calls ≤ 20,000
1 ≤ word.length(), prefix.length() ≤ 2000
All input strings contain only lowercase English letters.
No method uses null as a parameter value.

Notes

The Trie is initially empty.
countWordsStartingWith(prefix) counts all inserted words having the given prefix.
If no inserted word starts with the given prefix, return 0.

Examples

Example 1

Trie trie = new Trie()
trie.insert(word = "apple")
trie.insert(word = "app")
trie.countWordsStartingWith(prefix = "app") = 2

Explanation:
The inserted words are "apple" and "app". Both start with "app", so the answer is 2.

Example 2

Trie trie = new Trie()
trie.insert(word = "apple")
trie.insert(word = "apple")
trie.insert(word = "application")
trie.countWordsStartingWith(prefix = "app") = 3
trie.countWordsStartingWith(prefix = "apple") = 2

Explanation:
The word "apple" was inserted twice, so both insertions must be counted. The words starting with "app" are "apple", "apple", and "application".

Example 3

Trie trie = new Trie()
trie.insert(word = "cat")
trie.insert(word = "car")
trie.insert(word = "dog")
trie.countWordsStartingWith(prefix = "ca") = 2
trie.countWordsStartingWith(prefix = "do") = 1
trie.countWordsStartingWith(prefix = "z") = 0

Explanation:
Two inserted words start with "ca", one inserted word starts with "do", and none start with "z".