String

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi