Problem Description
Given an array of strings called products and a string called searchWord, design a system that suggests at most three product names after each character of searchWord is typed. The suggested products must share a common prefix with searchWord. If there are more than three matching products, return the three lexicographically smallest ones. The final output is a list of lists representing the suggestions after each character of searchWord is typed.
Key Insights
- Sorting the products lexicographically simplifies finding candidates.
- Using binary search helps efficiently locate the starting index for each prefix.
- Limiting suggestions to at most three candidates for every prefix ensures optimal performance in both time and space.
- Alternative methods include Trie-based search which can be efficient for prefix queries, but binary search after sorting is straightforward given the problem constraints.
Space and Time Complexity
Time Complexity: O(n log n + m log n) where n is the number of products and m is the length of searchWord. Sorting takes O(n log n) and for each of the m prefixes, binary search takes O(log n). Space Complexity: O(m + k) where m is the output size (list of lists for each prefix) and k is the additional space used by the sorting algorithm (which can be O(n) in worst-case depending on implementation).
Solution
The approach starts by sorting the input products lexicographically. For each prefix of searchWord, use binary search to quickly find the first product that could match the current prefix. Then, iterate through at most three products from that position and, if they share the prefix, add them to the suggestions for that stage. This process is repeated for every prefix in searchWord. This method leverages efficient sorting and binary search to meet the problem's requirements while ensuring the suggestions are lexicographically minimal.