1268：搜索推荐系统（1573 分）

力扣第 164 场周赛第 3 题

题目

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

分析

典型的字典树，在每个节点都保存该前缀的产品列表即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
	T = lambda: defaultdict(T)
	trie = T() 
	for w in products:
		p = trie
		for c in w:
			p = p[c]
			p['#'] = p.get('#', [])+[w]
	res, p = [], trie
	for c in searchWord:
		p = p[c]
		res.append(nsmallest(3, p.get('#', [])))
	return res

156 ms

*附加

还有个巧妙的方法：

• 将 products 排序后，某个前缀的产品列表必然是连续的
• 因此，在 products 中二分查找前缀的位置 i，判断 [i,i+2] 的产品是否符合即可

1
2
3
4
5
6
7
8

def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
	products.sort()
	res, q = [], ''
	for c in searchWord:
		q += c
		pos = bisect_left(products, q)
		res.append([s for s in products[pos:pos+3] if s.startswith(q)])
	return res

36 ms