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
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 题目总结