Count Strings with Given Prefix

Two counters per node instead of one boolean

time O(L) per operationspace O(total characters)

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.

Details

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").

Problem:Count Strings with Given PrefixMedium

Two counters per node instead of one boolean

step 1 / 15

•

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

Every step in words

Show all 15 steps

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).
insert("apple"): character 'a' has no child yet — create it and step in. Its prefixCount is now 1 (one word has passed through so far).
insert("apple"): character 'p' has no child yet — create it and step in. Its prefixCount is now 1 (one word has passed through so far).
insert("apple"): character 'p' has no child yet — create it and step in. Its prefixCount is now 1 (one word has passed through so far).
insert("apple"): character 'l' has no child yet — create it and step in. Its prefixCount is now 1 (one word has passed through so far).
insert("apple"): character 'e' has no child yet — create it and step in. Its prefixCount is now 1 (one word has passed through so far).
The walk for "apple" is done — mark this node as a word end. wordEnd at "apple" is now 1.
insert("app") again: the whole path root → a → ap → app already exists — nothing is created, every node on it just gets prefixCount + 1 (now 2 at "app").
Mark "app" as a word end again. wordEnd is now 1 — this node has now been the end of 1 separate inserts.
insert("app") again: the whole path root → a → ap → app already exists — nothing is created, every node on it just gets prefixCount + 1 (now 3 at "app").
Mark "app" as a word end again. wordEnd is now 2 — this node has now been the end of 2 separate inserts.
countWordsEqualTo("app"): walk the existing path root → a → ap → app — every link already exists.
Read the wordEnd counter at "app": 2. That is exactly how many times "app" was inserted — no scanning required.
countWordsStartingWith("ap"): walk root → a → ap the same way — a prefix query only needs the path to exist.
Read the prefixCount counter at "ap": 3. Three inserted words ("apple", "app", "app") all passed through this node.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Count Strings with Given Prefix in the editor All Trie problems Back to roadmap