Search Suggestions (Trie / Prefix)

Problem
Given a product list and a search word typed character by character, return up to 3 lexicographically smallest product suggestions for each prefix of the word.

Input / Output

• Input: products, a list of product names; word, the search string.
• Output: for each prefix of word, a list of up to 3 suggestions.

Constraints

• 1 <= n <= 10^4
• Suggestions for a prefix must be the lexicographically smallest matching products.

Example

• products = [mobile, mouse, moneypot], word = mou → suggestions returned for prefixes m, mo, mou.