Solutions to LeetCode 1268 Search Suggestions System
LeetCode 1268
Search Suggestions System (Medium) [link]
1] Brute Force Solution. Time complexity O(S * L) where S is the length of the searchWord and L is the number of words in products.
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
products.sort()
res = []
for i in range(len(searchWord)):
tmp = []
for word in products:
if searchWord[:i+1] == word[:i+1]:
tmp.append(word)
if len(tmp) <= 3:
res.append(tmp)
else:
tmp.sort()
res.append(tmp[:3])
return res
2] Using Trie. Time complexity O(sum(L) + S) where sum(L) is the sum of all lengths of products and S is the length of the searchWord.
class Trie:
def __init__(self):
self.child = dict()
self.words = list()
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
def addWord(root, word):
cur = root
for ch in word:
if ch not in cur.child:
cur.child[ch] = Trie()
cur = cur.child[ch]
cur.words.append(word)
cur.words.sort()
if len(cur.words) > 3:
cur.words.pop()
root = Trie()
for word in products:
addWord(root, word)
ans = list()
cur = root
flag = False
for ch in searchWord:
if flag or ch not in cur.child:
ans.append(list())
flag = True
else:
cur = cur.child[ch]
ans.append(cur.words)
return ans
