Prefix Popularity Counts
MediumTries & Strings
Problem
A product catalogue holds a list of item codes words (duplicates count separately). For each string in prefixes, report how many codes in the catalogue start with it.
Return the counts in the same order as prefixes.
Example 1
- Input:
- words = ["card","care","cart","dog","do"], prefixes = ["car","ca","d","do","dot","x"]
- Output:
- [3, 3, 2, 2, 0, 0]
"car" starts card, care and cart; "do" starts dog and do itself.
Example 2
- Input:
- words = ["a","a","ab"], prefixes = ["a","ab","abc"]
- Output:
- [3, 1, 0]
Both copies of "a" count.
Constraints
- 1 ≤ words.length, prefixes.length ≤ 2·10^4
- 1 ≤ length of each string ≤ 100
- Lowercase English letters only.
Hint
Show the first hint
Checking every word for every prefix repeats the same comparisons many times.
Walkthrough
How to approach it
01Clarify before coding
- Do duplicate words count twice? Yes, each entry in the list is one item.
- Does a word count as starting with itself? Yes: "do" starts with "do".
- Is a prefix longer than every word possible? Yes, the answer is then 0.
02Brute force
For each prefix, loop over all words and test startsWith.
Cost: O(Q·N·L): 2·10^4 · 2·10^4 · 100 = 4·10^10 character checks in the worst case.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.