Search Suggestions System

Problem Summary

• Given a list of products in strings and a search word
• Your task is to return 3 products for each letter typed

Key Observations

• Build a prefix tree (Trie)

Approach Taken

• For each node in the Trie we need to store 3 products that are recommended for that letter

Why This Works

• When you're iterating through the search word's characters and going through your Trie, you can simply use the suggestions build up so far at each level

Time & Space Complexity

• Time: $O(nlogn\ast L)$ → Reason: $L$ being average length of the product, $n$ being number of products. Sorting is dominant for this approach.
• Space: $O(n\ast L)$ → Reason: Number of products $\ast$ Average length of product. Basically storing each product in the Trie.

Code

class TrieNode:
    def __init__(self):
        self.children = {}
        self.suggestions = []

class Solution:
    def suggestedProducts(
        self, products: List[str], searchWord: str
    ) -> List[List[str]]:
        # pre-sort products
        products.sort()

        # first part: store all products in a prefix tree
        # at each letter we need to store the first three words, store the current working word if not hit the 3 limit
        prefixTreeRoot = TrieNode()

        for product in products:
            cur = prefixTreeRoot
            for letter in product:
                if letter not in cur.children:
                    cur.children[letter] = TrieNode()
                cur = cur.children[letter]
                if len(cur.suggestions) < 3:
                    cur.suggestions.append(product)

        # second part: get 3 product recommendation for each letter typed in searchWord
        suggestions = [[] for _ in range(len(searchWord))]
        cur = prefixTreeRoot
        for i, letter in enumerate(searchWord):
            if letter not in cur.children:
                return suggestions
            cur = cur.children[letter]
            suggestions[i] = cur.suggestions
        return suggestions

Common Mistakes / Things I Got Stuck On

• Iterating through other characters in the searchWord even after reaching if letter not in cur.children:
  • Once you have reached the dead-end, no further character would match
  • Keeping an output list and just updating it is the simplest