How many words start with this

Given a list of words and a list of prefixes, report for each prefix how many of the words begin with it.

Worked example#

Words [apple, app, apply, banana], prefixes [app, appl, ban, cat]:

So the answer is 3 2 1 0.

The idea#

Checking each prefix against every word costs the number of words times the length of the prefix, for every query. With many words and many queries that is far too slow, and it re-reads the same shared beginnings over and over.

A trie stores the words as a tree of characters, so shared beginnings are stored once. apple, app and apply share a path a → p → p, and only diverge after that.

Then the whole answer to a prefix query is: walk the prefix down the tree and read a number off the node you land on.

For that to work, each node records how many words pass through it. Count it on the way in as each word is inserted:

insert(word):
    node = root
    for each character:
        node = node.child(character), creating it if missing
        node.passing += 1

A query walks the prefix. Fall off the tree and the answer is zero. Land somewhere, and passing is the answer, already counted.

What it costs#

Inserting is the total length of all the words, once. Each query is the length of that prefix, and does not depend on how many words there are at all. That independence is the point of a trie: a million words and a five-character prefix is five steps.

A hash map of every prefix of every word would answer just as fast, and would store the same beginnings again and again. The trie stores each shared beginning once, which is why it is the structure that scales with a dictionary.

Where this shape turns up#

Autocomplete is this query. Spell check is this walk with backtracking when a character does not match. Word search on a grid is that same walk driven by the board instead of by a string, which is why tries and backtracking are taught together.

Constraints#

• 1 <= words, prefixes <= 20000
• Lowercase letters only, each word and prefix at most 20 characters

About the input#

A count then that many words, then a count then that many prefixes.