1268. Search Suggestions System - Detailed Explanation

Problem Statement

Given an array of strings called products and a string searchWord, design a system that suggests at most three product names from products after each character of searchWord is typed. The 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.

For each character typed (i.e. for each prefix of searchWord), return a list of up to three suggestions.

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": all products starting with "m" are considered. The three lexicographically smallest are returned.
    • "mo": similar to "m".
    • "mou": only "mouse" and "mousepad" start with "mou".
    • "mous" and "mouse": suggestions remain the same as in "mou".

• Example 2:

  • Input:

    products = ["havana"]
    searchWord = "havana"
    

  • Output:

    [["havana"], ["havana"], ["havana"], ["havana"], ["havana"], ["havana"]]
    

  • Explanation:
    Since there is only one product, it is returned for every prefix.

• Example 3:

  • Input:

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

  • Output:

    [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]
    

  • Explanation:
    Each prefix of "bags" produces a list of matching products up to three suggestions.

Constraints:

• The length of products and each product string can vary.
• searchWord is a non-empty string.
• All strings consist of lowercase English letters.
• If no product has a prefix matching the current prefix of searchWord, return an empty list for that step.

Hints for the Solution

• Hint 1:
  Notice that suggestions must be sorted lexicographically. Sorting the products array first can simplify the process of selecting the smallest suggestions.

• Hint 2:
  For each prefix of searchWord, you need an efficient way to find products starting with that prefix. Think about binary search on the sorted array to quickly locate the starting index of products matching the prefix.

Approaches to Solve the Problem

1. Brute Force Approach

Idea:
For each prefix of searchWord, loop through the entire products array, check if each product starts with the prefix, then sort the filtered list and pick up to three items.

Steps:

• For every prefix of searchWord, iterate through each product.
• Check whether the product starts with the prefix.
• Sort the valid products lexicographically.
• Choose the first three suggestions.

Downside:

• This approach can be inefficient if products is large, as each prefix requires scanning all products.

2. Optimal Approach Using Sorting and Binary Search

Idea:

1. Sort the products:
   Sorting the products lexicographically ensures that the suggestions are in order.
2. For each prefix:
   Use binary search to find the first product that starts with the current prefix.
3. Collect suggestions:
   From the found index, check up to three products to see if they start with the prefix and add them to the suggestion list.

Steps:

• Step 1: Sort the products array.
• Step 2: For every character in searchWord, build the prefix incrementally.
• Step 3: Use binary search (or a similar method) to locate the insertion point for the prefix in the sorted array.
• Step 4: Check the next three products (if available) to see if they share the prefix and add them to the result.

Benefits:

• The binary search reduces the search time per prefix to O(log n).
• The overall approach is efficient, with most work done during the initial sort and then simple lookups for each prefix.

3. Trie-Based Approach (Alternative Variation)

Idea:
Build a Trie (prefix tree) from the products array. For each node in the Trie, maintain a list of up to three lexicographically smallest words that pass through that node. Then, for each prefix of searchWord, traverse the Trie to get the suggestions directly.

Note:

• The Trie-based solution can be efficient for multiple queries but is more complex to implement.
• The sorting and binary search method is often preferred for its simplicity.

Code Implementations

Python Code Implementation