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, that is 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.

This question belongs to the trie pattern. A trie, also called a prefix tree, stores one node per character, so every word that shares a prefix shares a path from the root. A sorted array with binary search answers the same query, and both solutions appear below. Design Gurus teaches the problem in the Search Suggestions System lesson of Grokking the Coding Interview.

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 whether 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 when products is large, because 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 come out 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 whether they start with the prefix, then 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, where available, to see whether 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. Most of the work happens during the initial sort, and each prefix then needs only a simple lookup.

3. Trie-based approach (alternative variation)

Idea: Build a trie from the products array. At each node of the trie, keep a list of up to three lexicographically smallest words that pass through that node. Then, for each prefix of searchWord, walk the trie to the node for that prefix and read its stored suggestions directly.

The node structure itself is the subject of Implement Trie (Prefix Tree), which is worth solving first.

Note:

• The trie solution can be efficient for many queries over the same products, but it takes more code to implement.
• The sorting and binary search method is often preferred for its simplicity.

Code implementations

Python code implementation