time O(M + L)
space O(M)
R
b
c
a
a
t
p
r
t
Initialize Trie and insert all sorted products.
Pseudocode
Pseudocode
1class TrieNode:
2 children = {}
3 isWord = false
4function searchSuggestion(products, searchWord):
5 trie = new Trie()
6 products.sort()
7 for p in products:
8 trie.insert(p)
9 result = []
10 prefix = ''
11 node = trie.root
12 for char in searchWord:
13 prefix += char
14 if node and char in node.children:
15 node = node.children[char]
16 result.push(node.getTop3Words())
17 else:
18 node = null
19 result.push([])
20 return result