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 ofsearchWordis typed.
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:
1
2
3
Input: products =["havana"], searchWord ="havana"Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]Explanation: The only word "havana" will be always suggested while typing the search word.
To solve this problem, we need to return a list of up to three lexicographically smallest product names that match the prefix formed by the characters typed so far in searchWord.
Sorting the Products: Since we need lexicographically smallest products, we start by sorting the products array.
Prefix Matching: For each character typed in searchWord, we can iteratively match all product names to find the ones that start with the prefix formed so far.
Iterative Filtering:
Build the prefix incrementally.
Filter the sorted product list for names matching the prefix.
Store at most three matches in the result.
Use binary search techniques (if applicable for optimisation) or iterate through the array for prefix matching.
Sorting the products: O(n * log(n)), where n is the length of products.
For each prefix, filtering through products: O(n * m), where m is the length of searchWord. So total complexity is approximately O(n * log(n) + m * n).
Using a Trie data structure can significantly optimise prefix matching in this problem. Here’s the reasoning, approach, and implementation for solving it with a Trie.
A Trie is a tree-based data structure used for efficiently storing strings. Each node represents a character. Using a Trie, we can:
Quickly insert products into the structure with their prefixes.
Efficiently find all product names matching a prefix by traversing nodes.
We will preprocess the products list into a Trie, then for each prefix formed by searchWord, perform a traversal to obtain at most three lexicographically smallest suggestions.
Building the Trie: O(n * l), where n is the number of products and l is their average length.
Querying the Trie: O(m * k), where m is the length of searchWord, and k is the branching factor at each prefix (limited to 3 products stored per node).
Total: Approximately O(n * l + m * k).
Space: O(n * l). The Trie requires O(n * l) space for storing the products and associated nodes, where l is the average length of products.