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.
Each node in the Trie includes three parts:
children pointing to child nodes. For this problem, the array length is 26, which is the number of lowercase English letters. children[0] corresponds to the lowercase letter a, ..., children[25] corresponds to the lowercase letter z.v, representing the number of strings ending with this node.pv, representing the number of strings with this node as the prefix node.We start from the root of the Trie and insert the string. For the child node corresponding to the current character, there are two cases:
children array, then move to the child node along the pointer, and increase the pv value of the child node by 1. Continue to search for the next character.Repeat the above steps until the last character of the string is processed, then increase the v value of the current node by 1.
The time complexity is O(n), where n is the length of the string.
We start from the root of the Trie and search for the prefix. For the child node corresponding to the current character, there are two cases:
Repeat the above steps until a null pointer is returned or the last character of the prefix is searched.
The time complexity is O(n), where n is the length of the string.
We start from the root node of the Trie, and sequentially reduce the pv value of the corresponding child node by 1, until the last character of the string is searched. Then reduce the v value of the current node by 1.
The time complexity is O(n), where n is the length of the string.
| 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 |
LeetCode 1804. Implement Trie II (Prefix Tree) | Locked Question • 宰相小甘罗 • 462 views views
Watch 6 more video solutions →Practice Implement Trie II (Prefix Tree) with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor