Trie II Prefix Count LeetCode 1804

LeetCode 1804 Implement Trie II asks you to design a data structure that extends the classic Trie with frequency-counting capabilities. You must support four operations: insert(word) adds a word (duplicates are allowed), countWordsEqualTo(word) returns how many times the exact word has been inserted, countWordsStartingWith(prefix) returns how many inserted words begin with the given prefix, and erase(word) removes one occurrence of a word (guaranteed to exist at the time of the call).

Unlike LeetCode 208 (Implement Trie I) which only needs boolean presence checks, Trie II must track counts. Duplicate insertions are explicitly supported — inserting "apple" twice means countWordsEqualTo("apple") returns 2. Similarly, erase decrements rather than deletes, so erasing one of two "apple" insertions leaves countWordsEqualTo("apple") at 1.

The constraint that erase is only called on words guaranteed to exist simplifies the implementation — no need to validate existence before erasing. However, if you choose to prune zero-count nodes for space efficiency, you must be careful not to break other words that share the same prefix path.

The core extension over Trie I is simple: each TrieNode carries two integer counters in addition to its children dictionary. countPrefix records how many inserted words have passed through this node on their way to termination — it is incremented for every node visited during an insert. countWord records how many inserted words terminate at this exact node — it is incremented only at the final node of an insert.

With these two counters, both count queries become trivially O(m): countWordsEqualTo traverses the word character by character and returns the countWord of the final node (or 0 if the path does not exist). countWordsStartingWith traverses the prefix and returns the countPrefix of the node where the prefix ends (or 0 if the path does not exist). No subtree traversal, no recursion — just follow the path and read a counter.

The children field is typically implemented as a dictionary mapping characters to child TrieNodes, or as a fixed-size array of 26 slots (one per lowercase letter). The dictionary approach handles arbitrary alphabets and uses no memory for absent children; the array approach provides O(1) lookup with a slightly larger fixed overhead per node.

Insert traverses the word from left to right, creating TrieNodes as needed when a child for the current character does not exist. At each node along the path — including every intermediate node and the final terminal node — countPrefix is incremented by 1. At the final node only, countWord is also incremented by 1.

This means after inserting "apple", every node on the path from root to the final "e" node has countPrefix increased by 1, and the "e" node also has countWord increased by 1. Inserting "app" afterward increments countPrefix on the root, "a", "p", and "p" nodes again, and countWord on the second "p" node. The "e" node is unaffected by inserting "app".

Time complexity is O(m) where m is the length of the word. Space complexity per insert is O(m) in the worst case (all characters are new and require new nodes), but shared prefixes share nodes — the hallmark of trie efficiency.

countWordsEqualTo(word) traverses the trie following the characters of word one by one. If at any point the required child does not exist, the word was never inserted — return 0 immediately. If the full path exists, return the countWord value of the terminal node. This directly gives the number of times word was inserted minus the number of times it was erased.

countWordsStartingWith(prefix) works identically in its traversal: follow the characters of prefix, returning 0 if any child is missing. If the prefix path exists, return the countPrefix of the node where the prefix ends. Since countPrefix was incremented for every word that passed through that node, it equals precisely the number of currently stored words that begin with prefix.

Erase mirrors insert: traverse the word character by character along the existing path (the word is guaranteed to exist so no path-missing check is needed). At each node visited — every intermediate node and the final node — decrement countPrefix by 1. At the final node, also decrement countWord by 1.

After erasing, the counters accurately reflect the remaining word counts. If a node's countPrefix drops to 0, no remaining word passes through it — the subtree below is unreachable. You may optionally prune such nodes (set the parent's child pointer to null) for space efficiency, but this is not required for correctness and should be done carefully to avoid breaking shared paths.

Because the problem guarantees erase is called only on present words, you do not need to validate existence before erasing. The decrement operations are safe: countWord will not go below 0 for a word that exists, and countPrefix will not go below 0 because every node on the path was incremented when the word was inserted.

Python implementation: define a TrieNode class with children = defaultdict(TrieNode), countPrefix = 0, and countWord = 0. The Trie class holds self.root = TrieNode(). insert loops over characters, moves to children (auto-created by defaultdict), increments node.countPrefix at each step, then increments node.countWord at the end. countWordsEqualTo and countWordsStartingWith both traverse the path and return 0 on a missing child or the appropriate counter on success. erase traverses and decrements symmetrically to insert.

Java implementation: define a TrieNode class with TrieNode[] children = new TrieNode[26], int countPrefix = 0, int countWord = 0. In each operation, index into children using c - 'a'. For insert, create new TrieNode() when children[idx] is null. For count operations, return 0 when children[idx] is null. All four operations are O(m) and the code structure is nearly identical across them — traverse with a node pointer, update or read the appropriate counter at each step.

All four operations — insert, countWordsEqualTo, countWordsStartingWith, and erase — follow the exact same traversal pattern: start at root, follow characters, operate at each node. The only difference is what is read or modified: countPrefix is touched by all four, countWord only by insert, countWordsEqualTo, and erase.

LeetCode 208 Implement Trie (Prefix Tree) is the direct predecessor — Trie II extends it by replacing boolean end-of-word flags with integer counters. Mastering Trie I first makes the Trie II extension straightforward. The children structure, insertion traversal, and search traversal are identical; only the terminal node handling changes.

LeetCode 211 Design Add and Search Words Data Structure adds wildcard search ('.' matches any character) to a basic trie, requiring recursive or iterative backtracking at wildcard positions. LeetCode 212 Word Search II uses a trie to efficiently match multiple words against a 2D board via DFS, combining trie traversal with grid backtracking.

The Trie family extends further into problems like Replace Words (LeetCode 648), Stream of Characters (LeetCode 1032), and Maximum XOR of Two Numbers in an Array (LeetCode 421) which uses a binary trie. The counter extension in Trie II generalizes naturally — any time you need frequency information about prefixes or words in a collection, augmenting trie nodes with counters is the idiomatic approach.