【数据结构-Tire树】力扣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 中所有字符都是小写英文字母。

字典树

class Solution {
private:
    struct trie{
        vector<trie*> children;
        bool isEnd;
        trie():children(26, nullptr), isEnd(false){};
    };
    trie* root;
public:
    Solution(){
        root = new trie();
    }

    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        sort(products.begin(), products.end());
        for(string product : products){
            trie* node = root;
            for(char ch : product){
                ch -= 'a';
                if(node->children[ch] == nullptr){
                    node->children[ch] = new trie();
                }
                node = node->children[ch];
            }
            node->isEnd = true;
        }

        trie* node = root;
        vector<vector<string>> res;
        string prefix = "";
        bool noMatch = false;
        for(char c : searchWord){
            if(noMatch){
                res.push_back({});
                continue;
            }
            prefix += c;
            vector<string> ans;
            c -= 'a';
            if(node->children[c] == nullptr){
                noMatch = true;
                res.push_back({});
                continue;
            }
            node = node->children[c];
            FindWords(node, prefix, ans);
            res.push_back(ans);
        }
        return res;
    }

    void FindWords(trie* node, string& w, vector<string>& ans){
        if(ans.size() >= 3) return;
        if(node->isEnd){
            ans.push_back(w);
        }

        for(int i = 0; i < 26; i++){
            if(node->children[i] != nullptr){
                w.push_back(i + 'a');
                FindWords(node->children[i], w, ans);
                w.pop_back();
                if(ans.size() >= 3){
                    return;
                }
            }
        }
    }
};

这道题目的题目可能会有误导，实际上题目的意思就是要求你返回包含前缀且字典序最小的三个单词。

所以我们可以考虑使用字典树，将products的单词构造出字典树。接着我们可以根据不断遍历给出的searchWord单词在字典树中不断查找。

需要注意的是，我们在查找的时候，我们需要定义一个布尔型变量noMatch，也就是当在查找单词的时候，如果searchWord的前缀在字典树中没有任何单词匹配，那么在更长的前缀中也不可能有任何单词匹配，如果我们不使用noMarch，会导致可能在当前的单词返回{}，但是由于我们当前的node没有进行更新，所以在下一次调用children[c]的时候可能会导致node错误的更新。

还有一个需要注意的点是在递归的时候，我们传入FindWords函数的单词w可以直接使用&进行引用，避免大量进行复制和删除，从而在时间和空间上进行优化。