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.

#1268

Medium

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

搜索推荐系统

给你一个产品数组 products 和一个字符串 searchWord ， products 数组中每个产品都是一个字符串。请你设计一个推荐系统，在依次输入单词 searchWord 的每一个字母后，推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推…

数组字符串二分查找字典树排序

题目描述

给你一个产品数组 products 和一个字符串 searchWord ，products 数组中每个产品都是一个字符串。

请你设计一个推荐系统，在依次输入单词 searchWord 的每一个字母后，推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个，请按字典序返回最小的三个。

请你以二维列表的形式，返回在输入 searchWord 每个字母后相应的推荐产品的列表。

示例 1：

输入：products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
输出：[
["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]
]
解释：按字典序排序后的产品列表是 ["mobile","moneypot","monitor","mouse","mousepad"]
输入 m 和 mo，由于所有产品的前缀都相同，所以系统返回字典序最小的三个产品 ["mobile","moneypot","monitor"]
输入 mou， mous 和 mouse 后系统都返回 ["mouse","mousepad"]

示例 2：

输入：products = ["havana"], searchWord = "havana"
输出：[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]

示例 3：

输入：products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
输出：[["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

示例 4：

输入：products = ["havana"], searchWord = "tatiana"
输出：[[],[],[],[],[],[],[]]

提示：

1 <= products.length <= 1000
1 <= Σ products[i].length <= 2 * 10^4
products[i] 中所有的字符都是小写英文字母。
1 <= searchWord.length <= 1000
searchWord 中所有字符都是小写英文字母。

lightbulb

解题思路

方法一：排序 + 前缀树

题目要求在输入 searchWord 的每一个字母后，推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个，按字典序返回最小的三个。

找前缀相同的产品，可以使用前缀树；而要返回字典序最小的三个产品，我们可以先对 products 数组进行排序，然后将排序后的数组下标存入前缀树中。

前缀树的每个节点维护以下信息：

children：这是一个长度为 $26$ 的数组，用于存储当前节点的子节点，children[i] 表示当前节点的子节点中字符为 i + 'a' 的节点。
v：这是一个数组，用于存储当前节点的子节点中的字符在 products 数组中的下标，最多存储三个下标。

搜索时，我们从前缀树的根节点开始，找到每一个前缀对应的下标数组，将其存入结果数组中。最后只需要将每个下标数组中的下标对应到 products 数组中即可。

时间复杂度 $O(L \times \log n + m)$ ，空间复杂度 $O(L)$ 。其中 $L$ 是 products 数组所有字符串的长度之和，而 $n$ 和 $m$ 分别是 products 数组的长度和 searchWord 的长度。

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

37

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#792 匹配子序列的单词数 #692 前K个高频单词 #1170 比较字符串最小字母出现频次