String

1268. Search Suggestions System

An efficient one

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products.sort()
        w = ""
        res = []
        for c in searchWord:
            w += c
            idx = bisect.bisect_left(products, w)
            res.append([word for word in products[idx:idx+3] if word.startswith(w)])
        return res

Using trie

Image is from here

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        _END = '_END'
        trie = {}
        def build(word):
            curr = trie
            for c in word:
                curr = curr.setdefault(c, {})
            curr[_END] = _END
        for word in set(products):
            build(word)
        res = []
        curr = trie
        def dfs(curr, word):
            if len(words)==3:return
            if _END in curr:words.append(word)
            if len(words)==3:return
            for key in sorted(curr.keys()):
                if key!=_END:
                    dfs(curr[key], word+key)
            
        w = ""  
        for c in searchWord:
            w += c
            words = []
            if c not in curr:break
            dfs(curr[c],w)
            if not words:break
            res.append(words)
            curr = curr[c]
        return res + [[] for _ in range(len(searchWord)-len(res))]

More problems can use trie

208. Implement Trie (Prefix Tree)
1233. Remove Sub-Folders from the Filesystem
1032. Stream of Characters
1268. Search Suggestions System
211. Add and Search Word — Data structure design
676. Implement Magic Dictionary
677. Map Sum Pairs
745. Prefix and Suffix Search
425. Word Squares