Search Suggestions System

self.children = {}

Initialize a dictionary that maps characters to child TrieNode objects.

Each trie node must maintain references to its next characters so prefix traversal can proceed efficiently. Using a dictionary keyed by character enables constant-time lookup when inserting products and when traversing prefixes during queries.

self.suggestions = []

Initialize a list to store up to three product suggestions for this prefix.

Each node caches up to three lexicographically smallest products that share the prefix represented by this node. Storing these suggestions during trie construction allows prefix queries to return results instantly without searching or sorting at query time.

products.sort()

Sort the products array lexicographically.

Sorting ensures that when products are inserted into the trie, suggestions stored at each node are the lexicographically smallest, enabling efficient retrieval without further sorting.

if len(node.suggestions) < 3:

Check if the suggestions list at the current node has fewer than three products.

Limiting suggestions to three ensures memory efficiency and meets problem constraints for output size.

node.suggestions.append(word)

Append the current product to the suggestions list at the current node.

Appending products in sorted order guarantees that the suggestions list contains the lexicographically smallest products for the prefix represented by this node.

node.children[c] = TrieNode()

Create a new trie node for the current character if missing.

Adding new nodes ensures the trie accurately represents all prefixes of inserted products.

if node and c in node.children:

Check if current node exists and contains the current character as a child.

Verifying child existence ensures traversal continues only along valid prefix paths in the trie.

res.append(node.suggestions)

Append the suggestions list at the current node to the result.

Collecting the precomputed suggestions for the current prefix enables efficient retrieval without additional filtering or sorting.

else:

Handle the case where the prefix path does not exist in the trie.

Setting node to None signals that no further valid prefixes exist, ensuring subsequent prefixes yield empty suggestions.

root = TrieNode()

Create the root node of the trie.

The root node serves as the starting point for all insertions and prefix traversals, anchoring the trie structure.

if c not in node.children:

Check if the current character is not a child of the current node.

Detecting missing children nodes triggers creation of new trie nodes, expanding the trie to accommodate new prefixes.

node = node.children[c]

Move to the child node corresponding to the current character.

Advancing the node pointer allows insertion to proceed deeper into the trie along the product's prefix path.

node = root

Start traversal from the root node for prefix queries.

Beginning at the root allows traversal down the trie to find suggestions for each prefix of searchWord.

node = node.children[c]

Move to the child node corresponding to the current character.

Advancing the node pointer follows the prefix path to retrieve suggestions for the current prefix.

node = None

Set node to None to indicate no further traversal is possible.

This prevents invalid accesses and ensures empty suggestion lists for all remaining prefixes.

res.append([])

Append an empty list to the result for prefixes with no matches.

Appending empty lists maintains the output length and format, indicating no suggestions for these prefixes.

for word in products:

Iterate over each product to insert it into the trie.

Processing each product allows building the trie incrementally, ensuring all products contribute to the prefix suggestions.

node = root

Start insertion from the root node for the current product.

Resetting to root for each product ensures insertion begins at the top of the trie, correctly building the prefix paths.

for c in word:

Iterate over each character in the current product.

Processing characters sequentially builds the trie path representing the product's prefix structure.

res = []

Initialize the result list to store suggestions for each prefix.

This list accumulates the output for each prefix of searchWord, matching the problem's required return format.

for c in searchWord:

Iterate over each character in searchWord to build prefixes.

Processing each character incrementally forms prefixes for which suggestions are retrieved.

return res

Return the list of suggestion lists for all prefixes of searchWord.

Returning the accumulated results completes the solution, providing the required output format.