Search Suggestions System — Trie with Sorted Lists

Problem

Given a list of products and a search word, after each character typed return up to 3 lexicographically smallest products with that prefix.

Approach 1 — Sort + Binary Search

Sort products. For each prefix, binary search to find range. O(n log n + L * n) time.

Approach 2 — Trie with Sorted Lists

Insert sorted products into trie, at each node store up to 3 suggestions.

Solutions

Python — Sort + Binary Search

import bisect
class Solution:
    def suggestedProducts(self, products: list[str], searchWord: str) -> list[list[str]]:
        products.sort(); result=[]; prefix=""
        for c in searchWord:
            prefix+=c
            i=bisect.bisect_left(products,prefix)
            result.append([p for p in products[i:i+3] if p.startswith(prefix)])
        return result

Python — Trie

class Solution:
    def suggestedProducts(self, products: list[str], searchWord: str) -> list[list[str]]:
        root={}
        for p in sorted(products):
            node=root
            for c in p:
                if c not in node: node[c]={'#':[]}
                node=node[c]
                if len(node['#'])<3: node['#'].append(p)
        result=[]; node=root
        for c in searchWord:
            if node and c in node: node=node[c]; result.append(node['#'][:])
            else: node=None; result.append([])
        return result

Complexity

Binary Search: O(n log n + L * log n) | Trie: O(n*L + L)