Words under a prefix: hints, no solution
Easy · Tries
A search box shows how many catalogue words start with what the user has typed so far. You are given a list of lowercase words, which may contain repeats, and a list of lowercase query prefixes.
For every query, return how many words in the list start with it. A word equal to the query counts, and a word that appears several times counts once for each appearance. Return the counts in the same order as the queries. The words are loaded once and there can be many queries, so aim for time proportional to the total length of the words plus the total length of the queries.
Examples
- Input
- words = ["cart", "car", "card", "dog", "carbon"], queries = ["car", "ca", "d", "x"]
- Output
- [4, 4, 1, 0]
- Note
- Four words start with car, four with ca, one with d, and none with x.
- Input
- words = ["tap", "tap", "tape"], queries = ["tap", "tape", "tapes"]
- Output
- [3, 1, 0]
- Note
- The word tap appears twice and each appearance counts; tape is the only word starting with tape.
- Input
- words = [], queries = ["a"]
- Output
- [0]
- Note
- There are no words, so every count is zero.
Constraints
- 0 <= words.length <= 60000 and each word has 1 to 12 letters
- 1 <= queries.length <= 40000 and each query has 1 to 12 letters
- All words and queries use lowercase letters a to z
Hint 1: a nudge
Many words share the same beginning. Could you count, for each possible beginning, how many words pass through it, so that answering a query is only a lookup?
Unlock the full hints and timed practice with a pass
The second and third hints and the timed, runner-checked practice are part of a pass.