#1268

Medium

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Search Suggestions System

Design a search suggestion system that provides the top three lexicographically smallest products matching a search word at each keystroke.

array string binary search trie sorting

Problem Statement

You are given an array of strings called 'products' and a string 'searchWord'. The goal is to design a system that returns product suggestions as each character of the search word is typed. After each character, the system should provide at most three products that have a common prefix with the search word, sorted lexicographically in ascending order.

The system should return a list of lists, where each inner list contains up to three product suggestions that match the prefix typed so far. If more than three products match a prefix, only the lexicographically smallest three should be returned.

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

products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"]. After typing m and mo all products match and we show user ["mobile","moneypot","monitor"]. After typing mou, mous and mouse the system suggests ["mouse","mousepad"].

Example 2

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

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

The only word "havana" will be always suggested while typing the search word.

Constraints

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

Solution Approach

Brute Force with Sorting

A simple approach is to sort the product list lexicographically and for each character in the searchWord, filter the products that match the prefix and return the first three products. This method works efficiently if the input size is small, but the solution's time complexity will increase with larger datasets.

Binary Search Optimization

Since the product list is already sorted, binary search can be applied to find the range of products that match the current prefix efficiently. This reduces the number of comparisons and speeds up the solution, especially for longer input sizes.

Trie-based Approach

A more sophisticated approach involves using a trie (prefix tree) to store the product names. This allows us to efficiently retrieve all products with the same prefix and sort them in lexicographical order. This method can handle large datasets more effectively than brute force.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution depends on the chosen approach. The brute force method has a time complexity of O(n * m * log n) where n is the number of products and m is the length of the search word. The binary search approach can reduce the time complexity to O(n * log n + m * log n), while the trie-based approach offers the best performance with O(m * log n) for searching and insertion operations. Space complexity will depend on the trie size or the space required for storing the sorted product list.

What Interviewers Usually Probe

The candidate is expected to demonstrate knowledge of binary search or trie structures and how to apply them to optimize search performance.
Look for an understanding of lexicographical sorting and how to handle prefixes efficiently during search.
The candidate should be able to analyze time and space complexity based on different approaches, such as brute force, binary search, and trie.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding of lexicographical order and prefix matching, leading to incorrect product suggestions.
Inefficient brute force approach for larger datasets, resulting in performance issues.
Not considering the edge cases where the search word or product list may be small, which could lead to unnecessary complexity in the solution.

Follow-up variants

Consider variations where more than three product suggestions are required or where products are dynamically added or removed.
Modify the approach to handle non-unique products or case-insensitive searches.
Implement the solution for a scenario where the search space is constrained by additional filters (e.g., category or price).

FAQ

What is the primary algorithm pattern used in this problem?

This problem mainly uses binary search over the valid answer space to efficiently find the matching products for a given prefix.

How can I optimize the brute force solution?

You can optimize it by sorting the product list and using binary search to quickly locate the range of products that match the prefix.

Why would I use a trie in this problem?

A trie allows for efficient storage and retrieval of products based on their prefixes, reducing the time complexity of finding matching products.

What is the time complexity of the optimal solution?

The optimal solution using binary search or a trie has a time complexity of O(m * log n), where m is the length of the search word and n is the number of products.

What are common pitfalls to avoid in this problem?

Common pitfalls include incorrect handling of lexicographical order, inefficient brute force methods for large inputs, and not considering edge cases like small product lists or short search words.

terminal

Solution

Solution 1: Sorting + Trie

The problem requires that after each letter of the input `searchWord`, recommend up to three products from the `products` array that have the same prefix as `searchWord`. If there are more than three products with the same prefix that can be recommended, return the three with the smallest lexicographic order.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

class Trie:
    def __init__(self):
        self.children: List[Union[Trie, None]] = [None] * 26
        self.v: List[int] = []

    def insert(self, w, i):
        node = self
        for c in w:
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                node.children[idx] = Trie()
            node = node.children[idx]
            if len(node.v) < 3:
                node.v.append(i)

    def search(self, w):
        node = self
        ans = [[] for _ in range(len(w))]
        for i, c in enumerate(w):
            idx = ord(c) - ord('a')
            if node.children[idx] is None:
                break
            node = node.children[idx]
            ans[i] = node.v
        return ans


class Solution:
    def suggestedProducts(
        self, products: List[str], searchWord: str
    ) -> List[List[str]]:
        products.sort()
        trie = Trie()
        for i, w in enumerate(products):
            trie.insert(w, i)
        return [[products[i] for i in v] for v in trie.search(searchWord)]

Continue Practicing

#792 number of matching subsequences #692 top k frequent words #1170 compare strings by frequency of the smallest character