AlgoViz
HomeTrie

Prefix Matching

Medium

Walk the prefix, read the count

Problem

Given a dictionary of words and query prefixes, count (or list) how many words start with each query prefix.

In simple words

Store words in a trie with prefix counts; the count at a prefix's node is the answer.

The idea

Store a running count at every node of how many inserted words pass through it. Answering how many words start with a prefix is then a walk down the prefix followed by reading a single number, rather than scanning the dictionary.

The trick

  • Increment the pass-through count on every node during insert.
  • A missing node means zero matches — stop immediately.
  • O(prefix length) per query, whatever the dictionary size.
•catr

Step 1 of 5. The trie already stores "cat" and "car". Insert "cap" — walk down, creating nodes only where they're missing.

1/5
Optimal
timeO(L)spaceO(L)

Descend one node per letter.

1insert(word) {2  let node = this.root;3  for (const ch of word) {4    if (!node.children.has(ch)) node.children.set(ch, new TrieNode());5    node = node.children.get(ch);6  }7  node.isEnd = true;8}

Input

nodes
5, 4 edges

Memory

matched
—

Output

created
—
inserted
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Example

Input:
words=['apple','app','apply'], prefix='app'
Output:
3

Finished the walkthrough? Add it to your streak.