Watch 7 video solutions for Implement Trie II (Prefix Tree), a medium level problem involving Hash Table, String, Design. This walkthrough by 宰相小甘罗 has 462 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
Trie() Initializes the trie object.void insert(String word) Inserts the string word into the trie.int countWordsEqualTo(String word) Returns the number of instances of the string word in the trie.int countWordsStartingWith(String prefix) Returns the number of strings in the trie that have the string prefix as a prefix.void erase(String word) Erases the string word from the trie.
Example 1:
Input
["Trie", "insert", "insert", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsEqualTo", "countWordsStartingWith", "erase", "countWordsStartingWith"]
[[], ["apple"], ["apple"], ["apple"], ["app"], ["apple"], ["apple"], ["app"], ["apple"], ["app"]]
Output
[null, null, null, 2, 2, null, 1, 1, null, 0]
Explanation
Trie trie = new Trie();
trie.insert("apple"); // Inserts "apple".
trie.insert("apple"); // Inserts another "apple".
trie.countWordsEqualTo("apple"); // There are two instances of "apple" so return 2.
trie.countWordsStartingWith("app"); // "app" is a prefix of "apple" so return 2.
trie.erase("apple"); // Erases one "apple".
trie.countWordsEqualTo("apple"); // Now there is only one instance of "apple" so return 1.
trie.countWordsStartingWith("app"); // return 1
trie.erase("apple"); // Erases "apple". Now the trie is empty.
trie.countWordsStartingWith("app"); // return 0
Constraints:
1 <= word.length, prefix.length <= 2000word and prefix consist only of lowercase English letters.3 * 104 calls in total will be made to insert, countWordsEqualTo, countWordsStartingWith, and erase.erase, the string word will exist in the trie.Problem Overview: Design a Trie (prefix tree) that supports insert, countWordsEqualTo, countWordsStartingWith, and erase. Unlike the basic Trie problem, you must track how many times a word or prefix appears.
Approach 1: Store All Words in Hash Map (Brute Force) (Time: O(N * L), Space: O(N * L))
Keep a hash map where keys are full words and values store their frequency. insert increments the count, and countWordsEqualTo becomes a direct hash lookup. For countWordsStartingWith, iterate through every stored word and check if it starts with the prefix using string comparison. This approach is easy to implement but inefficient when many words exist because each prefix query scans the entire dataset. Useful only for small inputs or quick prototypes involving hash tables and strings.
Approach 2: Trie with HashMap Children (Time: O(L) per operation, Space: O(N * L))
Build a standard Trie where each node stores children in a hash map keyed by character. Each node maintains two counters: how many words pass through the node (prefixCount) and how many end at the node (endCount). During insert, traverse character by character, creating nodes if needed and updating counters. Prefix queries follow the path of the prefix and return prefixCount. This avoids scanning all words and makes operations proportional only to the word length.
Approach 3: Trie with Fixed Array (Optimal) (Time: O(L) per operation, Space: O(26 * nodes))
Instead of a hash map, each Trie node stores a fixed array of size 26 for lowercase English letters. Character transitions use index = c - 'a', giving constant-time child access. Maintain two counters per node: prefixCount (how many words pass through) and endCount (how many words end here). insert increments both counters appropriately, countWordsEqualTo reads endCount, countWordsStartingWith reads prefixCount, and erase decrements counts while traversing the path. Array indexing is faster and more memory predictable than hash maps, making this the preferred design solution.
Recommended for interviews: The array-based Trie is the expected solution. It demonstrates understanding of Trie structure, prefix counting, and efficient character indexing. Mentioning the brute-force hash map approach shows baseline reasoning, but implementing the Trie with counters proves you can design scalable string data structures.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Hash Map of Words (Brute Force) | O(N * L) | O(N * L) | Small datasets or quick prototype without building a Trie |
| Trie with HashMap Children | O(L) | O(N * L) | Flexible character sets or when alphabet size is large |
| Trie with Fixed Array | O(L) | O(26 * nodes) | Interview standard for lowercase strings; fastest lookups |