C++刷LeetCode（1268. 搜索推荐系统）【字典树】

糖逗

题目描述：

1. 给你一个产品数组 products 和一个字符串 searchWord ，products  数组中每个产品都是一个字符串。
   
2. 
   
3. 请你设计一个推荐系统，在依次输入单词 searchWord 的每一个字母后，推荐 products 数组中前缀与 searchWord 相同的最多三个产品。如果前缀相同的可推荐产品超过三个，请按字典序返回最小的三个。
   
4. 
   
5. 请你以二维列表的形式，返回在输入 searchWord 每个字母后相应的推荐产品的列表。
   
6. 
   
7.  
   
8. 
   
9. 示例 1：
   
10. 
    
11. 输入：products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
    
12. 输出：[
    
13. ["mobile","moneypot","monitor"],
    
14. ["mobile","moneypot","monitor"],
    
15. ["mouse","mousepad"],
    
16. ["mouse","mousepad"],
    
17. ["mouse","mousepad"]
    
18. ]
    
19. 解释：按字典序排序后的产品列表是 ["mobile","moneypot","monitor","mouse","mousepad"]
    
20. 输入 m 和 mo，由于所有产品的前缀都相同，所以系统返回字典序最小的三个产品 ["mobile","moneypot","monitor"]
    
21. 输入 mou， mous 和 mouse 后系统都返回 ["mouse","mousepad"]
    
22. 示例 2：
    
23. 
    
24. 输入：products = ["havana"], searchWord = "havana"
    
25. 输出：[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
    
26. 示例 3：
    
27. 
    
28. 输入：products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
    
29. 输出：[["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]
    
30. 示例 4：
    
31. 
    
32. 输入：products = ["havana"], searchWord = "tatiana"
    
33. 输出：[[],[],[],[],[],[],[]]
    
34.  
    
35. 
    
36. 提示：
    
37. 
    
38. 1 <= products.length <= 1000
    
39. 1 <= Σ products[i].length <= 2 * 10^4
    
40. products[i]&#160;中所有的字符都是小写英文字母。
    
41. 1 <= searchWord.length <= 1000
    
42. searchWord&#160;中所有字符都是小写英文字母。
    
43. 
    
44. 来源：力扣（LeetCode）
    
45. 链接：https://leetcode-cn.com/problems/search-suggestions-system
    
46. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class Solution {
   
2. private:
   
3.     //字典树的结构
   
4.     struct Trie{
   
5.         vector<int> word_id;
   
6.         map<char, Trie*>next;
   
7.     };
   
8. public:
   
9.     vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
   
10.         //构建字典树
    
11.         int len = products.size();
    
12.         Trie* root = new Trie();
    
13.         for(int i = 0; i < len; i++){
    
14.             string word = products[i];
    
15.             Trie* node = root;
    
16.             for(auto cha : word){
    
17.                 if((node -> next).count(cha) == 0){
    
18.                     node -> next[cha] = new Trie();
    
19.                 }
    
20.                 node = node -> next[cha];
    
21.                 (node -> word_id).push_back(i);
    
22.             }
    
23.         }
    
24.         //搜索
    
25.         vector<vector<string> >res;
    
26.         Trie* node = root;
    
27.         int store_ = -1;
    
28.         for(int i = 0; i < searchWord.size(); i++){
    
29.             vector<string>store;
    
30.             if((node -> next).count(searchWord[i]) != 0){
    
31.                 node = node -> next[searchWord[i]];
    
32.                 for(auto id : (node -> word_id)){
    
33.                     store.push_back(products[id]);
    
34.                 }
    
35.                 sort(store.begin(), store.end());
    
36.                 if(store.size() > 3){
    
37.                     res.push_back(vector<string>(store.begin(), store.begin() +3));
    
38.                 }else{
    
39.                     res.push_back(store);
    
40.                 }
    
41.             }else{
    
42.                 store_ = i;
    
43.                 break;
    
44.             }
    
45.         }
    
46.         for(int i = store_; i < searchWord.size(); i++){
    
47.             res.push_back(vector<string>());
    
48.         }
    
49.         return res;
    
50.     }
    
51. };

复制代码