Search Suggestions System

Problem

E-commerce search boxes show product suggestions on every keystroke. After each character typed, the system must return up to 3 matching products sorted lexicographically. Given a list of products and a search word, return a list of suggestion lists - one per character of the search word.

Example 1:

Input: products = ["solar","saturn","sock","soda"], searchWord = "socks"
Output: [
  ["saturn","sock","soda"],    after 's'
  ["sock","soda","solar"],     after 'so'
  ["sock"],                    after 'soc'
  ["sock"],                    after 'sock'
  []]                          after 'socks'
Explanation: after each keystroke, up to 3 products with the typed prefix are returned in lexicographic order.

Example 2:

Input: products = ["pack","paddle","palm"], searchWord = "pad"
Output: [
  ["pack","paddle","palm"],    after 'p'
  ["pack","paddle","palm"],    after 'pa'
  ["paddle"]]                  after 'pad'

Constraints:

• 1 <= products.length <= 500
• 1 <= products[i].length <= 1000
• 1 <= sum(products[i].length) <= 10^4
• All the strings of products are unique.
• products[i] consists of lowercase English letters.
• 1 <= searchWord.length <= 500
• searchWord consists of lowercase English letters.

Solution Breakdown

Approach: Trie navigation to the prefix node, then a bounded sorted DFS for the top 3 completions.

Insert every product into a trie. For each prefix of the search word, get_suggestions first walks the trie character by character to the prefix node; if any character is missing it returns [] early, since no product carries that prefix (and therefore every longer prefix is empty too). From the prefix node, _dfs collects complete words into a shared results list, seeded with path = list(prefix) so each recorded word includes the prefix itself. Two details make the output correct: the children are iterated with sorted(node.children), so the DFS descends alphabetically and naturally emits words in lexicographic order; and len(results) >= 3 is checked at the top of every call, so the recursion stops the instant three suggestions are gathered. A word is recorded as "".join(path) only when node.is_end is True - joining the mutable path into a fresh string so later append/pop mutations cannot corrupt an already-stored result. The driver builds the list of prefixes with search_word[:i+1] for each i and returns one suggestion list per keystroke.

Edge cases: A prefix matching nothing yields [], as do all subsequent (longer) prefixes. Capping at 3 means deep subtrees are pruned early. Appending and popping path around each recursive call keeps the path correct across sibling branches.

Complexity: O(sum of product lengths) to build the trie; each keystroke is O(prefix length) to navigate plus a DFS bounded by 3 results, so O(L) where L is the search word length times bounded collection - O(sum of product lengths) space.