class Solution:
def suggestedProducts(self, words: List[str], query: str) -> List[List[str]]:
"""
tc O(NlgN+L^2*lg(N)) sc O(L) L: len(query)
1. sort the dictionary
2. iterate query to concatenate prefix of query
3. for each prefix, find the index where everything previously is smaller than current prefix
4. start from current index up to 3 steps further, check if corresponding word start with prefix, if qualify, put into top3 as current partial query's response
5. append top3 into res array
"""
words.sort()
prefix = ''
res = []
for c in query:
prefix += c
idx = bisect.bisect_left(words,prefix)
top3 = []
for i in range(idx, min(len(words),idx+3)):
if words[i].startswith(prefix): # tc O(L)
top3.append(words[i])
res.append(top3)
return res
Trie Solution
class TrieNode:
def __init__(self):
self.children = {}
self.same_prefix = []
class Trie:
def __init__(self):
self.root = TrieNode()
#tc O(W) sc O(W)
def insert(self, word):
cur = self.root
for c in word:
if c not in cur.children:
cur.children[c] = TrieNode()
cur = cur.children[c]
if len(cur.same_prefix) < 3:
cur.same_prefix.append(word)
# tc O(L) sc O(1)
def search(self,query):
res = []
cur = self.root
for i,c in enumerate(query):
if c in cur.children:
cur = cur.children[c]
res.append(cur.same_prefix)
else:
res.extend([[]]*(len(query)-i))
return res
return res
class Solution:
def suggestedProducts(self, words: List[str], query: str) -> List[List[str]]:
""" tc O(NlgNW + L) W: avg len of word L: len of query
sc O(N*W)
"""
root = Trie()
for word in sorted(words):
root.insert(word)
return root.search(query)