How do you approach Count Words With Given Prefix?

Build one trie from the words. Each node stores how many words pass THROUGH it.

What is the time complexity of Count Words With Given Prefix?

Time complexity: O(sum of word lengths) to build, O(prefix length) per query.. Space complexity: O(sum of word lengths).

What are common mistakes on Count Words With Given Prefix?

Leaving out the end-of-word flag, so a lookup reports words that were never inserted. Allocating a fixed 26-child array per node for a sparse alphabet, when a map keeps the memory honest. Not handling the empty string, which is a valid prefix of everything.

gitGood.dev

← Back to problems

Count Words With Given Prefix

EasyData Structures

Description

Given a list of `words` and a list of `prefixes`, return for each prefix how many words start with it. Return the counts in the same order as `prefixes`. A word counts as starting with itself: `"app"` starts with `"app"`. This is the smallest problem that shows why a trie exists. Scanning every word for every prefix is O(prefixes x words x length); a trie answers each prefix in time proportional to the prefix alone.

Example 1

Input: words = ["apple","app","apricot","banana"], prefixes = ["app","ap","b","c"]

Output: [2,3,1,0]

Example 2

Input: words = ["hello","help","helium"], prefixes = ["hel","help","he"]

Output: [3,1,3]

Example 3

Input: words = ["a"], prefixes = ["a","aa"]

Output: [1,0]

Constraints

- 0 <= words.length <= 10^4 - 0 <= prefixes.length <= 10^4 - 1 <= word length, prefix length <= 100 - All strings are lowercase English letters.

Count Words With Given Prefix: approach, complexity and pitfalls

An easy trie problem, graded against 6 test cases (3 of them hidden).

The pattern: Trie

A prefix tree for fast string lookup by shared prefix.

Reach for it when you see: Many words, repeated prefix queries, autocomplete, or word-search over a grid.

More Trieproblems →

If you are stuck

Show the 3-step hint ladder

Build one trie from the words. Each node stores how many words pass THROUGH it.
Increment that counter on every node you touch while inserting a word - not just the final node.
To answer a prefix, walk it from the root. If you fall off the trie, the answer is 0; otherwise it is the counter stored at the node you land on.

The optimal approach

Show the approach: Count on the way down, not at the end

A trie stores words as a character tree, so all words sharing a prefix share the path that spells it. The trick here is what each node holds: not "is this the end of a word" but how many words pass through this node.

On insert, bump that counter at every node along the path. Then a prefix query is just a walk: follow the prefix's characters from the root, and the counter at the node you land on is the answer - already computed, no subtree traversal needed. Falling off the trie means no word has that prefix, so the answer is 0.

The cost model is what makes this worth learning. The naive nested scan is O(P x W x L). The trie pays O(total characters) once to build, then O(prefix length) per query - independent of how many words there are. With 10^4 words and 10^4 prefixes that is the difference between hundreds of millions of character comparisons and a few hundred thousand.

Time: O(sum of word lengths) to build, O(prefix length) per query.
Space: O(sum of word lengths)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Empty input. At least one case passes an empty collection. Make sure your loop bounds and any "first element" read survive a length of zero.
Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.

Common Trie mistakes

These apply to the pattern as a whole, not just this problem.

Leaving out the end-of-word flag, so a lookup reports words that were never inserted.
Allocating a fixed 26-child array per node for a sparse alphabet, when a map keeps the memory honest.
Not handling the empty string, which is a valid prefix of everything.