How many words start with this?
Count, at every node, how many words pass through it, updated as each word is inserted. About 9 minutes.
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.
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["#"]Insert "cat": every node on the path gets + 1.
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.
Inserting "cat", "car" and "cow". What is the count at the node for "c"?
- A3
- B2
Show the answer
3. All three words start with c, so every one of them increases the c node's count by 1.
How many words start with this?
words is a list of lowercase words. Return how many words in words start with prefix.
words = ["cat", "car", "cow", "dog"], prefix = "c" → 3
0 ≤ words.length ≤ 1,000 · 1 ≤ words[i].length, prefix.length ≤ 30 · every word is lowercase a-z