Search Suggestions System

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.

Examples

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:

• 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"].

Example 2:

Input: products = ["havana"], searchWord = "havana"

Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

Explanation: Only one product matches at every prefix.

Example 3:

Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"

Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

Constraints

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