939. Distinct Prefixes
Given n words, print how many distinct non-empty prefixes they have in
total, counting each distinct prefix once however many words share it.
For ab and abc the distinct prefixes are a, ab and abc, so the
answer is 3.
This is exactly the number of nodes in the trie, not counting the root. Every node is reached by one distinct prefix and every distinct prefix reaches one node, so building the trie and counting the nodes IS the answer.
Collecting every prefix into a hash set gives the same number and does substantially more work, because it stores each shared prefix once per word before deduplicating it.
Constraints - `1 ≤ n ≤ 20000` - Every word is 1 to 20 lowercase English letters.
Input
The first line contains an integer n.
The next n lines each contain one word.
Output
Print one integer: the number of distinct non-empty prefixes across all the words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.