Distinct prefixes
Count every node the trie actually needed to create, which is the number of distinct prefixes overall. About 8 minutes.
Counting creations, not steps
Insert every word as usual, but keep a counter that only goes up when a brand-new node has to be made. Walking into a node that already exists, because an earlier word passed through it, doesn't count again: that beginning was already known.
It is like counting the distinct roads on a map rather than the trips taken along them.
count = 0
if c not in node:
node[c] = {}
count += 1 # a new prefix- created
- 0
An empty trie: just the root, which isn't a prefix.
What this number means
This count is exactly the number of nodes in the finished trie, other than the root. It measures how much the words actually overlap.
A list of totally different words needs almost one node per letter. A list of words sharing long beginnings needs far fewer, because the shared roads are built only once.
words = ["cat", "car"]. How many distinct prefixes are there?
- A4
- B6
Show the answer
4. "c", "ca" are shared; "cat" and "car" each add one more distinct prefix: 4 in total.
Distinct prefixes
words is a list of lowercase words. Return how many distinct, non-empty prefixes exist across all of words combined (a prefix shared by several words is counted once).
words = ["cat", "car"] → 4
0 ≤ words.length ≤ 1,000 · 1 ≤ words[i].length ≤ 30 · every word is lowercase a-z