Given n keywords, count the number of distinct non-empty strings that occur as a prefix of at least one keyword (each keyword is a prefix of itself). Equivalently, this is the number of nodes, other than the root, in the trie built from the keywords.
Duplicate keywords contribute no new prefixes. All keywords consist of lowercase English letters only.
Line 1: an integer n.
Line 2: n space-separated keywords.
A single integer: the number of distinct non-empty prefixes.
Example 1
Input
2 ab abc
Expected
3
Explanation
The distinct prefixes are a, ab, abc, giving 3.
Example 2
Input
3 a a b
Expected
2
Explanation
The distinct prefixes are a and b; the duplicate a adds nothing, giving 2.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →