A counter at every node

Give every node a counter that starts at 0. While inserting a word, every node the walk passes through, including newly created ones, gets its counter raised by 1.

After all words are inserted, a node's counter is exactly how many words share the beginning that ends at that node. It is like a turnstile on each junction counting how many words walked through.

Every node visited: gets plus one while inserting a word, not just the last.

A query is a lookup: walk to the prefix's node, then read its counter.

In code

root = {"#": 0}
for w in words:
    node = root
    for c in w:
        if c not in node:
            node[c] = {"#": 0}
        node = node[c]
        node["#"] += 1
node = root
for c in prefix:
    if c not in node:
        return 0
    node = node[c]
return node["#"]

words = [cat, car, cow, dog] · each node counts the words that pass through it

Insert "cat": every node on the path gets + 1.

Move 1 of 5

Missing prefix means zero

If the walk for the prefix falls off the trie, meaning some letter has no child, then no word ever shared that beginning. Nobody walked that road, so nobody went through the turnstile.

The answer is 0 straight away, and there is nothing to read.

Missing letter: answer 0 immediately, since there is no counter to read.