Search Suggestions System

Explanation & Solution

Description

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 a common prefix with searchWord. If there are more than three products with a common prefix, return the three lexicographically smallest products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Input:products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"

mobile

mouse

moneypot

monitor

mousepad

Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]

Explanation:

After typing "m", products with prefix "m" are ["mobile","moneypot","monitor","mouse","mousepad"]. The 3 lexicographically smallest are ["mobile","moneypot","monitor"].
After typing "mo", products with prefix "mo" are ["mobile","moneypot","monitor","mouse","mousepad"]. The 3 smallest are ["mobile","moneypot","monitor"].
After typing "mou", products with prefix "mou" are ["mouse","mousepad"].
After typing "mous", products with prefix "mous" are ["mouse","mousepad"].
After typing "mouse", products with prefix "mouse" are ["mouse","mousepad"].

Constraints

1 <= products.length <= 1000
1 <= products[i].length <= 3000
1 <= searchWord.length <= 1000
All strings consist of lowercase English letters

Approach

Trie pattern

1. Sort Products Lexicographically

Sort the products array so that when we insert into the trie, the first products we encounter at each node are the lexicographically smallest

2. Build a Trie with Suggestions

Create a TrieNode with children and a suggestions array (max size 3)
Insert each product into the trie character by character
At each node along the insertion path, if the node has fewer than 3 suggestions, add the current product
Since products are sorted, the first 3 added are guaranteed to be the lexicographically smallest

3. Search by Prefix

Traverse the trie one character at a time following the characters of searchWord
At each node, the suggestions array is the answer for that prefix
If a character is not found in the trie, all remaining prefixes return empty arrays

4. Collect Results

For each character typed in searchWord, push the current node's suggestions (or an empty array) into the results
Return the final list of suggestion lists

Key Insight

Sorting first and storing at most 3 suggestions per trie node avoids expensive lookups at query time
Each query character takes O(1) time, and the trie is built in **O(N * L)** where N is the number of products and L is the average product length
Overall time complexity: **O(N * L * log N) for sorting + O(N * L) for trie construction + O(M)** for searching, where M is the length of searchWord

Solution Code

Map Sum Pairs

Maximum XOR of Two Numbers in an Array