Given an array of strings products and a string searchWord. We want to 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 the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.
Return 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"]]
Example 4:
Input: products = ["havana"], searchWord = "tatiana" Output: [[],[],[],[],[],[],[]]
Constraints:
1 <= products.length <= 1000products.1 <= Σ products[i].length <= 2 * 10^4products[i] are lower-case English letters.1 <= searchWord.length <= 1000searchWord are lower-case English letters.
The description was taken from https://leetcode.com/problems/search-suggestions-system/.
class TrieNode:
def __init__(self, val:str) -> None:
self.val = val
self.children = {}
self.end_here = False
self.word = ""
class Trie: def __init__(self) -> None:
self.root = TrieNode(None)
def insert(self, word:str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode(char)
node = node.children[char]
node.end_here = True
node.word = word
def starts_with(self, word:str) -> TrieNode:
node = self.root
for char in word:
if char not in node.children:
return None
node = node.children[char]
return node
def dfs(self, search:str) -> List[str]:
stack, output = [], []
prefix = self.starts_with(search)
if not prefix:
return []
stack.append(prefix)
while stack:
if len(output) == 3:
break
node = stack.pop()
if node.end_here:
output.append(node.word)
for child in sorted(node.children, reverse=True):
next_node = node.children[child]
stack.append(next_node)
return output
class Solution: def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
trie = Trie()
for product in products:
trie.insert(product)
output = []
for i in range(len(searchWord)):
output.append(trie.dfs(searchWord[:i+1]))
return outputThis problem is a slightly easier version of Design Search Autocomplete System which is also here on AlgoNinjutsu.
If we are wanting to traverse common prefixes, that is usually an indication that a Prefix Tree, a Trie, could be applied.
What we can do is traverse the given products list and insert the characters into a Trie. Once they are in the Trie, we will continuously add one character to the search word prefix that we will be plugging into a Depth-First Search to get the other words that share the same prefix.
Once we have three words for a given prefix, we will return the output of the results and expand the prefix.
Let's start out by creating a TrieNode class. This will define the building blocks of our Trie.
Each Trie node will have a character value, a dictionary of children for constant lookup, a flag to signal the end of a word input, and a word that will give us its upper branch in constant time.
class TrieNode:
def __init__(self, val:str) -> None:
self.val = val
self.children = {}
self.end_here = False
self.word = ""
Next, we will have a Trie class for building the Trie.
class Trie:
A root will be initialized with a null character value once the Trie class has been instantiated.
def __init__(self) -> None:
self.root = TrieNode(None)
Let's also make a function for inserting character nodes into our Trie.
def insert(self, word:str) -> None:
We will start by creating a node pointer at the root of the Trie.
Then for each character within the given word, if they don't exist within the Trie already, meaning we don't currently have a common prefix in the Trie to this given word, we will instantiate a character node and place it in the children of the uncommon prefix branch of the Trie then iterate to it.
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode(char)
node = node.children[char]
Once we have finished placing each character node or traversing them if they already existed, we will set the last character node of the word's end_here flag to true then set its word to the word input so that we can access it later during our DFS.
node.end_here = True
node.word = word
We could also use a starts_with function to traverse prefixes and return the last node of the prefix so that we can find what similar words come after it within the Trie inside the node's children.
def starts_with(self, word:str) -> TrieNode:
We will initialize a node pointer at the root of the Trie, and for each character node within the given word, if they don't exist within the Trie yet then we have nothing to return. Otherwise, we will keep moving down until we have finished the prefix and return the last character node of the prefix.
node = self.root
for char in word:
if char not in node.children:
return None
node = node.children[char]
return node
The last helper function we will make is a dfs function to return results of similar words of the given search prefix.
def dfs(self, search:str) -> List[str]:
Let's initialize a stack and an output.
stack, output = [], []
Next, we will get the last node of the given prefix by passing our search prefix to our starts_with method.
prefix = self.starts_with(search)
If the given prefix was not common among any branches within the Trie, we have nothing to return.
if not prefix:
return []
Otherwise, we will push it onto our stack and begin our DFS.
stack.append(prefix)
While we still have nodes on the stack and haven't found three results yet for the given prefix, we will continue our search.
while stack:
if len(output) == 3:
break
We'll pop a node off the stack and see if it ends its branch, meaning it is the last node of a complete word.
If that's the case we will pass the word to the output.
node = stack.pop()
if node.end_here:
output.append(node.word)
Otherwise, we will pass its child nodes onto the stack.
However, one important detail from the problem description is if we have multiple words that could be derived from the given common prefix, we need to return the lowest words ordered lexicographically. To do this, we will sort the child nodes before we push them onto the stack because stacks and DFS, in general, are LIFO: Last In First Out.
That means that if we place child word branches onto the stack, the first branch that will be explored will now be the first in sorted order since we are sorting those and pushing them onto the stack before their sibling branches.
for child in sorted(node.children, reverse=True):
next_node = node.children[child]
stack.append(next_node)
Once we have our three or fewer results, we will return them.
return output
Lastly, we just need to make use of our helper functions to get our results.
We will start by instantiating a Trie, then we will push each product into the trie.
trie = Trie()
for product in products:
trie.insert(product)
Then, we will initialize our output array.
output = []
Now, all we have to do is iterate through each character from the search word and passing each current prefix into our DFS function, expanding one character at a time during each iteration.
for i in range(len(searchWord)):
output.append(trie.dfs(searchWord[:i+1]))
Once we have all of our results for each prefix, we will return them.
return output