C++刷LeetCode（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 <= 1000
1 <= Σ products[i].length <= 2 * 10^4
products[i] 中所有的字符都是小写英文字母。
1 <= searchWord.length <= 1000
searchWord 中所有字符都是小写英文字母。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-suggestions-system
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
private:
    //字典树的结构
    struct Trie{
        vector<int> word_id;
        map<char, Trie*>next;
    };
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        //构建字典树
        int len = products.size();
        Trie* root = new Trie();
        for(int i = 0; i < len; i++){
            string word = products[i];
            Trie* node = root;
            for(auto cha : word){
                if((node -> next).count(cha) == 0){
                    node -> next[cha] = new Trie();
                }
                node = node -> next[cha];
                (node -> word_id).push_back(i);
            }
        }
        //搜索
        vector<vector<string> >res;
        Trie* node = root;
        int store_ = -1;
        for(int i = 0; i < searchWord.size(); i++){
            vector<string>store;
            if((node -> next).count(searchWord[i]) != 0){
                node = node -> next[searchWord[i]];
                for(auto id : (node -> word_id)){
                    store.push_back(products[id]);
                }
                sort(store.begin(), store.end());
                if(store.size() > 3){
                    res.push_back(vector<string>(store.begin(), store.begin() +3));
                }else{
                    res.push_back(store);
                }
            }else{
                store_ = i;
                break;
            }
        }
        for(int i = store_; i < searchWord.size(); i++){
            res.push_back(vector<string>());
        }
        return res;
    }
};