class Solution {
public:
vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
}
};
1268. 搜索推荐系统
给你一个产品数组 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 <= 10001 <= Σ products[i].length <= 2 * 10^4products[i] 中所有的字符都是小写英文字母。1 <= searchWord.length <= 1000searchWord 中所有字符都是小写英文字母。原站题解
python3 解法, 执行用时: 144 ms, 内存消耗: 22.3 MB, 提交时间: 2022-12-05 15:54:35
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
# 字符串按字典序排列
products.sort()
# 构建Trie树
trie={}
dic=collections.defaultdict(list)
for word in products:
root=trie
for i,c in enumerate(word):
dic[word[:i+1]].append(word)
if c not in root:
root[c]={}
root=root[c]
res=[]
# 搜索
for i,c in enumerate(searchWord):
res.append(dic[searchWord[:i+1]][:3])
return res
java 解法, 执行用时: 6 ms, 内存消耗: 45 MB, 提交时间: 2022-12-05 15:53:43
class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
Arrays.sort(products);
List<List<String>> ans = new ArrayList<>();
int n = searchWord.length();
int left = 0;
int right = products.length;
for(int i = 0; i < n; i++){
char c = searchWord.charAt(i);
while (left<right&&(products[left].length()<=i || products[left].charAt(i)<c)) ++left;
while (left<right&&products[right-1].length()>i&&products[right-1].charAt(i)>c) --right;
List<String> curr = new ArrayList<>();
for(int j = left; j < right&&j<left+3; j++){
curr.add(products[j]);
}
ans.add(curr);
}
return ans;
}
}
python3 解法, 执行用时: 56 ms, 内存消耗: 18 MB, 提交时间: 2022-12-05 15:53:07
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
products.sort()
query = ""
iter_last = 0
ans = list()
for ch in searchWord:
query += ch
iter_find = bisect.bisect_left(products, query, iter_last)
ans.append([s for s in products[iter_find : iter_find + 3] if s.startswith(query)])
iter_last = iter_find
return ans
python3 解法, 执行用时: 172 ms, 内存消耗: 22 MB, 提交时间: 2022-12-05 15:52:43
class Trie:
def __init__(self):
self.child = dict()
self.words = list()
class Solution:
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
def addWord(root, word):
cur = root
for ch in word:
if ch not in cur.child:
cur.child[ch] = Trie()
cur = cur.child[ch]
cur.words.append(word)
cur.words.sort()
if len(cur.words) > 3:
cur.words.pop()
root = Trie()
for word in products:
addWord(root, word)
ans = list()
cur = root
flag = False
for ch in searchWord:
if flag or ch not in cur.child:
ans.append(list())
flag = True
else:
cur = cur.child[ch]
ans.append(cur.words)
return ans