1268. Search Suggestions System

Option 1: 直觉用trie + search (hashmap or dfs)

Given M products and avg length of each product is N

time complexity
- sort O(M * log(M)) (string comparison is simplified to O(1))
- build trie time complexity is O(M * N) where M*N is total number of trie nodes
- search O(N) to traverse the prefix in trie
space complexity
- O(M * N) trine nodes
- worst case each trie node contains all the M words

1.1 trie + hash

class TrieNode:
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.words = []

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products.sort() # so words are appended to cur.words in order
        root = self.buildTrie(products)
        return self.search(root, searchWord)
        
    def buildTrie(self, products: List[str]) -> 'TrieNode':
        root = TrieNode()
        for product in products:
            cur = root
            for ch in product:
                cur = cur.children[ch]
                cur.words.append(product)
                if len(cur.words) > 3:
                    cur.words.pop()
        return root
    
    def search(self, root: TrieNode, searchWord: str) -> List[List[str]]:
        res = []
        cur = root
        for i, ch in enumerate(searchWord):
            if ch in cur.children:
                cur = cur.children[ch]
                res.append(cur.words)
            else:
                for j in range(i, len(searchWord)):
                    res.append([])
                break
            
        return res

1.2 Trie + dfs

Given M products and avg length of each product is N

time complexity
- build trie time complexity is O(M * N) where M*N is total number of trie nodes
- search
  - for loop N * (trie traversal O(N) + dfs O(26 * N * 3)) -> O(N^2)
space complexity O(M * N) for building trie

class TrieNode:
    def __init__(self):
        self.children = collections.defaultdict(TrieNode)
        self.word = None
        self.isWord = False

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        root = self.buildTrie(products)
        
        res = []
        prefix = ''
        for ch in searchWord:
            prefix += ch
            res.append(self.search(root, prefix))
        return res
        
    def buildTrie(self, products: List[str]) -> 'TrieNode':
        root = TrieNode()
        for product in products:
            cur = root
            for ch in product:
                cur = cur.children[ch]
            cur.isWord = True
            cur.word = product
        return root
    
    def search(self, root: TrieNode, prefix: str) -> List[str]:
        cur = root
        for ch in prefix:
            if ch in cur.children:
                cur = cur.children[ch]
            else:
                return []
        
        res = []
        self.dfs(cur, res)
        return res
        
    def dfs(self, root: TrieNode, res: List[str]) -> None:
        if not root or len(res) == 3:
            return 
        
        if root.isWord:
            res.append(root.word)
        
        cur = root
        for i in range(ord('a'), ord('z') + 1):
            ch = chr(i)
            if ch in cur.children:
                self.dfs(cur.children[ch], res)

Option 2: binary search (最优)

Given M products and avg length of each product is N

time complexity
- sort O(MN * log M) instead of O(M * log M) because string comparison is O(N) instead of O(1)
- external for loop N + binary search O(N * log M) instead of O(log M) because string comparison is O(N)
- O((M+N) * N * log M)
space complexity
- O(n) since python sort is build on a variant of merge sort

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products.sort()
        res, prefix = [], ''
        for ch in searchWord:
            res.append([])
            prefix += ch
            i = bisect.bisect_left(products, prefix)
            for word in products[i:i + 3]:
                if word.startswith(prefix):
                    res[-1].append(word)
        return res

1268. Search Suggestions System - cocoder39/coco39_LC GitHub Wiki