936. Words With a Given Prefix
You are given n words, then q queries. Each query is a prefix.
For every query, print how many of the words start with that prefix.
A hash set answers "is this a word" instantly and cannot answer this at all without examining every word it holds. A trie stores the shared prefixes once, so the count for a prefix is waiting at the node that prefix leads to.
Build it by walking each word character by character, creating nodes as needed, and incrementing a counter at every node you pass through. The counter at a node is then exactly how many words share that prefix.
Constraints - `1 ≤ n ≤ 20000` - `1 ≤ q ≤ 20000` - Every word and prefix is 1 to 20 lowercase English letters.
Input
The first line contains an integer n.
The next n lines each contain one word.
The next line contains an integer q.
The next q lines each contain one prefix to query.
Output
For each query, print one integer on its own line: how many words begin with that prefix.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.