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.

products = ["mobile","mouse","mango","maps"]
searchWord = "mouse"
→ [
    ["mango","maps","mobile"],   after 'm'
    ["mango","maps","mobile"],   after 'mo'
    ["mobile","mouse"],          after 'mou'
    ["mouse"],                   after 'mous'
    ["mouse"],                   after 'mouse'
  ]

Solution

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.