KK's blog

每天积累多一些

0%

LeetCode 1268 Search Suggestions System

Posted on Edited on Disqus:

LeetCode



You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed.

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: 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”]]


Example 3:

Input: products = [“bags”,”baggage”,”banner”,”box”,”cloths”], searchWord = “bags”
Output: [[“baggage”,”bags”,”banner”],[“baggage”,”bags”,”banner”],[“baggage”,”bags”],[“bags”]]


Constraints:

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

题目大意：

实现搜索结果为3个autocomplete的功能

Prefix解题思路(推荐)：

Prefix

解题步骤：

N/A

注意事项：

  1. 用Trie，另一种思路是用prefix，此法采用prefix法，将所有单词按前缀加入到字典中

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
	products.sort()
	prefix_dict = collections.defaultdict(list)
	for word in products:
		for i in range(len(word)):
			prefix = word[:i + 1]
			if len(prefix_dict[prefix]) < 3:
				prefix_dict[prefix].append(word)
	res = []
	for i in range(len(searchWord)):
		prefix = searchWord[:i + 1]
		res.append(prefix_dict[prefix])
	return res

算法分析：

时间复杂度为O(nL1 + L2)，空间复杂度O(nL1), L1为单词列表中最长的长度，L2为搜索单词长度，n为单词个数

Trie + DFS算法II解题思路：

建Trie，然后根据搜索的前缀定位到Trie节点，然后对此节点做DFS找到3个单词，因为DFS和字母顺序是一致的，所以DFS可行
具体参考Leetcode solution

Two pointers算法III解题思路：

先排序，用双指针相向搜索，根据搜索单词的每一个字母，不断收缩搜索范围，左指针和右指针之间即为满足条件的结果。每轮将左指针往后三个结果加到结果集
具体参考Leetcode discussion

Free mock interview