Loading...
Loading...
Loading...
The college library app has a search box. As a student types, the app shows how many book titles start with the letters typed so far.
You get n titles, each one lowercase word. The same title can appear more than once, and each copy counts. Then you get q prefixes. For each prefix, print how many titles start with it. A title also starts with itself.
Example
Input
6 apple app apply bat ball app 4 ap b appl cat
Output
4 2 2 0
ap matches apple, app, apply and app again: 4. b matches bat and ball. appl matches apple and apply. Nothing starts with cat.
Try the problem first. Open one hint at a time.
Checking every title for every prefix can take 10^4 × 10^4 steps. Share the work between titles that begin the same way.
Build a tree of letters: from each node, one child per next letter. A title becomes a path from the root.
At every node on a title's path, add 1 to a counter. That counter is the number of titles passing through that node.
For a prefix, walk its letters down the tree. If a letter is missing, the answer is 0. Otherwise print the counter where you stop.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor