[LeetCode] 1268. Search Suggestions System
2022/7/13 6:20:03
本文主要是介绍[LeetCode] 1268. Search Suggestions System,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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 of
products
are unique. products[i]
consists of lowercase English letters.1 <= searchWord.length <= 1000
searchWord
consists of lowercase English letters.
搜索推荐系统。
给你一个产品数组 products 和一个字符串 searchWord ,products 数组中每个产品都是一个字符串。
请你设计一个推荐系统,在依次输入单词 searchWord 的每一个字母后,推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个,请按字典序返回最小的三个。
请你以二维列表的形式,返回在输入 searchWord 每个字母后相应的推荐产品的列表。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/search-suggestions-system
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题题意很直观,我提供一个字典树的做法,参考了这个帖子。
代码不难理解,有几个细节提示一下。对于 products 数组里的每个单词,我们都把它 insert 到字典树里。因为之后我们在做 search 的时候需要返回相关的前缀 prefix,所以我们在 insert 的时候,每添加一个字母,我们就把当前这个 product 放入当前这个前缀的 suggestion 里,并一直保持 suggestion 是排序的且长度最大为 3。这样我们就能保证当我们 search 的时候,能返回字典序最小的三个 suggestion。
时间O(mn) - 创建字典树 + insert 每个单词
空间O(n)
Java实现
1 class Solution { 2 public List<List<String>> suggestedProducts(String[] products, String searchWord) { 3 Node root = new Node(); 4 for (String p : products) { 5 insert(p, root); 6 } 7 return search(searchWord, root); 8 } 9 10 private void insert(String product, Node root) { 11 Node node = root; 12 for (int i = 0; i < product.length(); i++) { 13 int j = product.charAt(i) - 'a'; 14 if (node.children[j] == null) { 15 node.children[j] = new Node(); 16 } 17 node = node.children[j]; 18 node.suggestion.offer(product); 19 Collections.sort(node.suggestion); 20 if (node.suggestion.size() > 3) { 21 node.suggestion.pollLast(); 22 } 23 } 24 } 25 26 private List<List<String>> search(String searchWord, Node root) { 27 List<List<String>> res = new ArrayList<>(); 28 for (char c : searchWord.toCharArray()) { 29 if (root != null) { 30 root = root.children[c - 'a']; 31 } 32 res.add(root == null ? Arrays.asList() : root.suggestion); 33 } 34 return res; 35 } 36 } 37 38 class Node { 39 Node[] children = new Node[26]; 40 LinkedList<String> suggestion = new LinkedList<>(); 41 }
LeetCode 题目总结
这篇关于[LeetCode] 1268. Search Suggestions System的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升