202. Count Words With a Given Prefix

Given n words and a prefix string, count how many of the words start with that prefix.

Input: The first line contains an integer n. The next n lines each contain one word. The final line contains the prefix string to search for. Output: Print a single integer - the count of words that start with the given prefix.

1 <= n <= 10^5

Storing a pass-through count at every trie node (not just at word-ending nodes) is the one small addition that turns a basic trie into a prefix-counting machine - the same small addition several other problems in this category also rely on.

Given a list of words and a prefix, count how many words in the list actually start with that exact prefix. Brute force: For each word, check directly whether it starts with the given prefix (a simple string-starts-with check) and count the matches - this is O(n * prefix length) per query, which is fine for one query but repeats a lot of redundant work if you have MANY prefix queries against the same word list. Optimised: By pre-building a trie ONCE with a pass-through count at every node, any future prefix query is answered by simply walking the prefix's own length, completely independent of how many total words exist in the list - the upfront cost of building the trie pays for itself the moment you have more than a handful of queries.

Sort all the words lexicographically once, which brings every word sharing a given prefix into one contiguous block. Then find the lower boundary (first word >= prefix) and upper boundary (first word >= the prefix with its last character incremented) using two binary searches; the number of words in between is exactly the count of words with that prefix, turning the problem into a range-size computation instead of a full scan. Time: O(n log n) Space: O(n)

For every word in the list, compare it character by character against the prefix, up to the prefix's length, and count the word if every corresponding character matches. This checks each of the n words independently, which is straightforward but does not scale well if the word list is queried against many different prefixes, since every query re-examines every word from scratch. Time: O(n * L) Space: O(1)

Insert every word into a trie (prefix tree), incrementing a counter stored at each node every time a word's construction passes through it. To answer the query, walk the trie following the characters of the prefix; if the walk completes without falling off the tree, the counter at that final node is exactly the number of words sharing that prefix. Each query then costs only the length of the prefix, with no rescanning or re-sorting needed. Time: O(sum of word lengths) to build, O(|prefix|) per query Space: O(sum of word lengths)

1. Build a trie from all the words, but at EVERY node, also keep a running count of how many words pass through that exact point. 2. To answer a prefix query, walk the trie following the prefix's letters one at a time. 3. If at any point the next letter has no branch, the answer is 0 - no word shares that much of the prefix. 4. If you successfully walk the whole prefix, the count stored at the node you land on is your answer.

Time: Building the trie takes time proportional to the total characters across all words (once); each query afterward only takes time proportional to the prefix's own length, not the number of words at all. Space: Proportional to the total characters across all words, for the trie structure itself.

Test a prefix matching every word, a prefix matching none, a prefix that equals a whole word while also being a prefix of longer words, and n=10^5 for performance.

Highlight the amortization argument explicitly: one trie build pays for itself across MANY prefix queries - this is exactly why a trie beats a naive per-query scan whenever queries repeat against the same fixed word list.