Search Box Suggestions
A shop's search box suggests products while the visitor types. The catalogue is the list catalog of distinct lowercase words, and the visitor types the word typed one letter at a time.
After each letter, the box shows up to three catalogue words that start with the letters typed so far, choosing the three that are smallest in dictionary order. Return a list with one entry per typed letter, each entry being the suggested words in dictionary order (an empty list when nothing matches).
A trie whose nodes remember their three smallest words answers each prefix quickly.
Example 1
Input: catalog = ["router","rotor","route","rope","roster","rover"], typed = "rout" Output: [["rope","roster","rotor"],["rope","roster","rotor"],["route","router"],["route","router"]] Explanation: "r" and "ro" both match every word; "rou" narrows it to route and router.
Example 2
Input: catalog = ["apple","app","apply"], typed = "bat" Output: [[],[],[]] Explanation: No word starts with "b".
Constraints
- 0 <= catalog.length <= 6000
- 1 <= catalog[i].length, typed.length <= 20
- All words are lowercase and distinct.
Hint 1
Sort the catalogue first, then insert the words into a trie.
Hint 2
While inserting in sorted order, let each node keep the first three words that pass through it.
Discussion 0
Join free to post in the discussion.
Good practice for: Frontend Developer, Backend Developer, Full Stack Developer, Mobile App Developer, AI Engineer (LLM & Generative AI)
Run checks your code on 2 sample tests. Submit runs all 7 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.