Medium · Trie Counters
Understand → Visualise → Practice.
A trie node represents a prefix. Incrementing a pass count during insertion makes each later prefix query proportional only to the prefix length.
For every inserted character, move to its child and increment that child's count.
Create missing character nodes.
Increment the node reached by each character.
Walk the prefix; missing means 0, otherwise return the final count.
O(total word characters + total query characters) time and O(total word characters) space.
Count words passing through a node, not only words ending there.
Read the full guide first: Tries and Prefix Search.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.