Pattern visualizer

Implement Trie II (Count Prefix)

The plain Trie only asks whether a word exists, so one boolean per node is enough. Counting asks a harder question — HOW MANY inserted words share this node — so each node instead carries two integers: prefixCount, bumped on every node the insert walk passes through, and wordEnd, bumped only on the node where a word finishes. Both queries then become a walk followed by reading one integer, no re-scanning. Animated on: Design a trie that supports insert(word), countWordsEqualTo(word) and countWordsStartingWith(prefix). insert("apple"), insert("app"), insert("app") again, then countWordsEqualTo("app") and countWordsStartingWith("ap")..

Two counters per node instead of one boolean

time O(L) per operationspace O(total characters)step 1 / 15

•

line 1

Start with an empty trie: just a root node. Every node tracks two counters — prefixCount (how many inserted words pass through it) and wordEnd (how many inserted words end exactly here).

Pseudocode

1FUNCTION insert(word):
2  cur <- root
3  FOR ch IN word:
4    IF ch NOT IN cur.children: cur.children[ch] <- new node
5    cur <- cur.children[ch]
6    cur.prefixCount <- cur.prefixCount + 1
7  cur.wordEnd <- cur.wordEnd + 1
8FUNCTION countWordsEqualTo(word):
9  cur <- walk(word)
10  RETURN cur = null ? 0 : cur.wordEnd
11FUNCTION countWordsStartingWith(prefix):
12  cur <- walk(prefix)
13  RETURN cur = null ? 0 : cur.prefixCount

← / → step · space play · Home restart

Where to practice Trie

Practice Trie problems All Trie problems Back to roadmap