LC 1268 [M] Search Suggestions System - ALawliet/algorithms GitHub Wiki

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products.sort()
        cur = ''
        ans = []
        for c in searchWord:
            cur += c
            i = bisect.bisect_left(products, cur)
            ans.append([product for product in products[i:i+3] if product.startswith(cur)])
        return ans

Sorting and searching cost O(n * m * log n) and O(L * m * logn), respectively; Therefore,
Time: O((n + L) * m * logn), space: O(L * m) - - including return list ans, but excluding space cost of sorting, where m = average length of products, n = products.length, L = searchWord.length().

class Trie:
    def __init__(self):
        self.sub = {}
        self.suggestion = []

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        root = Trie()
        for product in sorted(products):
            self._insert(product, root)
        return self._search(searchWord, root)    

    def _insert(self, product: str, root: Trie) -> None:
        trie = root
        for char in product:
            if char not in trie.sub:
                trie.sub[char] = Trie()
            trie = trie.sub[char]

            trie.suggestion.append(product)
            trie.suggestion.sort()
            if len(trie.suggestion) > 3:
                trie.suggestion.pop()

    def _search(self, searchWord: str, root: Trie) -> List[List[str]]:              
        ans = []
        for char in searchWord:
            if root:
                root = root.sub.get(char)
            ans.append(root.suggestion if root else [])            
        return ans

Complexity depends on the process of building Trie and the length of searchWord. Building Trie cost time O(m * m * n), due to involving comparing String, which cost time O(m) for each comparison. Therefore,
Time: O(m * m * n + L), space: O(m * n + L * m) - including return list ans, where m = average length of products, n = products.length, L = searchWord.length().