搜索推荐系统

标签: 字典树 数组 字符串 二分查找 排序 堆（优先队列）

难度: Medium

给你一个产品数组 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 中所有字符都是小写英文字母。

Submission

运行时间: 40 ms

内存: 18.9 MB

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        prod = products
        heapq.heapify(prod)
        res = []
        for i in range(len(searchWord)):
            tmp = []
            count = 0
            while  prod:
                if (i < len(prod[0]) and prod[0][0:i+1] != searchWord[0:i+1]) or (i >= len(prod[0])): 
                    heapq.heappop(prod)
                elif i < len(prod[0]) and prod[0][0:i+1] == searchWord[0:i+1]:
                    if count == 3:
                        break
           
                    count += 1
                    word = heapq.heappop(prod)
                    tmp.append(word)

            res.append(tmp)    
            for j in range(len(tmp)):
                heapq.heappush(prod, tmp[j])
        return res

Explain

该题解采用最小堆的方法来维护字典序的顺序，首先将所有的产品放入最小堆中。然后，对于搜索词的每个字符，它会遍历最小堆，检查堆顶元素的前缀是否与搜索词的当前前缀匹配。如果匹配，且已经选出的推荐产品少于3个，它将该产品加入临时列表并从堆中弹出。如果不匹配或已达到三个推荐产品的限制，它将停止当前字符的检查。在每个字符的推荐完成后，它将临时列表中的产品重新压入堆中以供下一轮使用。

时间复杂度: O(k n log n)

空间复杂度: O(n)

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        prod = products # 将产品列表赋值给prod
        heapq.heapify(prod) # 将prod列表转化为最小堆
        res = [] # 结果列表
        for i in range(len(searchWord)): # 对于searchWord中的每一个字符
            tmp = [] # 存储当前字符匹配的产品
            count = 0 # 计数器，用于确保不超过3个推荐产品
            while prod: # 当堆不为空时
                if (i < len(prod[0]) and prod[0][0:i+1] != searchWord[0:i+1]) or (i >= len(prod[0])): # 如果当前堆顶产品不匹配或长度不足
                    heapq.heappop(prod) # 从堆中弹出
                elif i < len(prod[0]) and prod[0][0:i+1] == searchWord[0:i+1]: # 如果匹配
                    if count == 3: # 如果已有3个推荐产品
                        break # 停止当前循环
                    count += 1 # 推荐产品计数器加1
                    word = heapq.heappop(prod) # 从堆中弹出当前产品
                    tmp.append(word) # 将当前产品添加到临时列表中
            res.append(tmp) # 将当前字符的推荐列表添加到结果中
            for j in range(len(tmp)): # 将临时列表中的产品重新压入堆中
                heapq.heappush(prod, tmp[j])
        return res # 返回结果

Explore

使用最小堆而不是直接对数组进行排序的主要原因是，最小堆可以更高效地处理动态数据集合。在这个算法中，需要频繁地插入和删除元素（每次检查一个字符后调整堆），最小堆可以在对数时间内完成这些操作，而对于排序数组，插入和删除操作可能需要线性时间。此外，使用最小堆可以直接访问当前最小的元素，这在实际操作中可以更快地找到匹配的前缀。

是的，如果堆顶的产品一旦被判断为不符合当前搜索条件并被弹出，它将不会在此次搜索中被重新考虑。这样做确实存在漏掉符合条件的产品的风险，特别是在搜索词的后续字符可能重新使这些产品变为符合条件的情况下。因此，这种方法可能需要更多的逻辑来确保不会漏掉符合条件的产品，或者在实现时采取不同的策略来确保所有可能的产品都被适当地考虑。

是的，将临时列表中的产品重新压回堆中确实可能导致在随后的搜索中重复检查这些产品，这可能会影响算法的效率。每次字符的推荐完成后，重新压入的产品将再次参与堆操作和匹配，可能增加了额外的计算负担。这种重复检查可以通过使用更加高效的数据结构或优化算法逻辑来减少。

在题解中，当searchWord的长度大于某个产品的长度时，该产品会在匹配过程中被弹出堆且不再被重新考虑，因为它不可能符合当前的搜索条件。这是因为如果产品长度已小于当前搜索词的长度，那么它无法匹配更长的搜索词前缀。这样的处理确保了只有那些长度足够并可能符合搜索要求的产品才会被考虑。