Suggest as you type: hints, no solution
Medium · Tries
A shop search box suggests products while the shopper types. Given a list of distinct lowercase product names in no particular order, and the text the shopper finally typed, return one list of suggestions for each typed character.
After the first i characters have been typed, the suggestions are the up to three alphabetically smallest product names that start with those i characters. Names are compared letter by letter, and a name that is a prefix of another comes before it. If no product matches, that step returns an empty list. The result has exactly as many lists as the typed text has characters.
Examples
- Input
- products = ["mouse", "mousepad", "moneypad", "monitor", "mobile"], typed = "mouse"
- Output
- [["mobile", "moneypad", "monitor"], ["mobile", "moneypad", "monitor"], ["mouse", "mousepad"], ["mouse", "mousepad"], ["mouse", "mousepad"]]
- Note
- After m, mo and mou the first three names alphabetically are listed; once mouse is complete only mouse and mousepad match.
- Input
- products = ["cable", "charger"], typed = "x"
- Output
- [[]]
- Note
- No product starts with x, so the only step has no suggestions.
- Input
- products = ["a"], typed = "ab"
- Output
- [["a"], []]
- Note
- After a only the product a matches; after ab nothing does.
Constraints
- 1 <= products.length <= 2000 and each name has 1 to 12 lowercase letters
- 1 <= typed.length <= 12
- Product names are distinct
Hint 1: a nudge
For a given typed prefix, which products qualify, and which three of those come first alphabetically? Would the answer change if you sorted the product list once at the start?
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.