You are given an array of strings products
and a string searchWord
.
Design a system that suggests at most three product names from products
after each character of searchWord
is typed. Suggested products should have common prefix with searchWord
. If there are more than three products with a common prefix return the three lexicographically minimums products.
Return a list of lists of the suggested products after each character of searchWord
is typed.
Example 1:
Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output: [
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]
After typing mou, mous and mouse the system suggests ["mouse","mousepad"]
Example 2:
Input: products = ["havana"], searchWord = "havana"
Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
Example 3:
Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]
Constraints:
-
1 <= products.length <= 1000
-
1 <= products[i].length <= 3000
-
1 <= sum(products[i].length) <= 2 * 104
- All the strings of
products
are unique. -
products[i]
consists of lowercase English letters. -
1 <= searchWord.length <= 1000
-
searchWord
consists of lowercase English letters.
SOLUTION:
class Node:
def __init__(self, val=None, children=[], end=False):
self.val = val
self.children = children
self.end = end
self.words = set()
class Trie:
def __init__(self):
self.root = Node(val=None, children=[])
def insert(self, word: str, pos) -> None:
n = len(word)
curr = self.root
for i, c in enumerate(word):
found = False
for node in curr.children:
if node.val == c:
curr = node
curr.words.add(pos)
found = True
break
if not found:
newcurr = Node(val=c, children=[])
newcurr.words.add(pos)
curr.children.append(newcurr)
curr = newcurr
curr.end = True
def startsWith(self, prefix: str):
n = len(prefix)
curr = self.root
for i, c in enumerate(prefix):
found = False
for node in curr.children:
if node.val == c:
curr = node
found = True
break
if not found:
return []
return curr.words
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
trie = Trie()
for i, p in enumerate(products):
trie.insert(p, i)
n = len(searchWord)
op = []
for i in range(1, n + 1):
res = trie.startsWith(searchWord[:i])
op.append(sorted([products[i] for i in res])[:3])
return op
Top comments (0)