1.题目
给你一个产品数组 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 * 104
products[i] 中所有的字符都是小写英文字母。
1 <= searchWord.length <= 1000
searchWord 中所有字符都是小写英文字母。文章来源:https://www.toymoban.com/news/detail-571194.html
2.思路
(1)前缀树
思路参考本题官方题解。文章来源地址https://www.toymoban.com/news/detail-571194.html
3.代码实现(Java)
//思路1————前缀树
class Solution {
public List<List<String>> suggestedProducts(String[] products, String searchWord) {
Trie trie = new Trie();
for (String product : products) {
trie.insert(product);
}
return trie.startWith(searchWord);
}
}
class Trie {
public static final int NUM = 26;
public static final int SIZE = 3;
Trie[] children;
PriorityQueue<String> queue;
public Trie() {
children = new Trie[NUM];
/*
s1.compareTo(s1) 方法是用于比较字符串 s1、s2 的字典顺序的方法。它返回一个整数,表示两个字符串的相对顺序:
(1) 如果返回值为 0,则表示两个字符串相等;
(2) 如果返回值小于 0,则表示字符串 s1 小于 s2;
(3) 如果返回值大于 0,则表示字符串 s1 大于 s2;
例如,"def".compareTo("abc") 的返回值为 3
*/
queue = new PriorityQueue<>((p1, p2) -> p2.compareTo(p1));
}
public void insert(String word) {
Trie node = this;
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (node.children[index] == null) {
node.children[index] = new Trie();
}
node = node.children[index];
node.queue.offer(word);
if (node.queue.size() > SIZE) {
node.queue.poll();
}
}
}
public List<List<String>> startWith(String word) {
Trie node = this;
boolean exist = true;
List<List<String>> res = new ArrayList<>();
for (int i = 0; i < word.length(); i++) {
int index = word.charAt(i) - 'a';
if (!exist || node.children[index] == null) {
exist = false;
res.add(new ArrayList<>());
continue;
}
node = node.children[index];
List<String> tmp = new ArrayList<>();
while (!node.queue.isEmpty()) {
tmp.add(node.queue.poll());
}
Collections.reverse(tmp);
res.add(tmp);
}
return res;
}
}
到了这里,关于LeetCode_前缀树_中等_1268.搜索推荐系统的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!