Problem Statement

Given a list of distinct strings products and a string searchWord.

Determine a set of product suggestions after each character of the search word is typed. Every time a character is typed, return a list containing up to three product names from the products list that have the same prefix as the typed string.

If there are more than 3 matching products, return 3 lexicographically smallest products. These product names should be returned in lexicographical (alphabetical) order.

Examples

1. Example 1:

   • Input: Products: ["apple", "apricot", "application"], searchWord: "app"
   • Expected Output: [["apple", "application", "apricot"], ["apple", "application", "apricot"], ["apple", "application"]]
   • Justification: For the prefix 'a', all three products match, listed in alphabetical order. The same holds for the prefix 'ap'. For the prefix 'app', "apple" and "application" match. Note that "application" comes before "apricot": their third letters differ, and 'p' sorts before 'r'.

2. Example 2:

   • Input: Products: ["king", "kingdom", "kit"], searchWord: "ki"
   • Expected Output: [["king", "kingdom", "kit"], ["king", "kingdom", "kit"]]
   • Justification: All products starting with "k" are "king", "kingdom", and "kit". The list remains the same for the 'ki' prefix.

3. Example 3:

   • Input: Products: ["fantasy", "fast", "festival"], searchWord: "farm"
   • Expected Output: [["fantasy", "fast", "festival"], ["fantasy", "fast"], [], []]
   • Justification: Initially, "fantasy", "fast", and "festival" match 'f'. Moving to 'fa', only "fantasy" and "fast" match. No product matches with "far", and "farm".

Constraints:

• 1 <= products.length <= 1000
• 1 <= products[i].length <= 3000
• 1 <= sum(products[i].length) <= 2 * 10⁴
• All the strings of products are unique.
• products[i] consists of lowercase English letters.
• 1 <= searchWord.length <= 1000
• searchWord consists of lowercase English letters.

Try it yourself

Try solving this question here: