1268. Search Suggestions System ---------M !!!!!!!

 Given an array of strings products and a string searchWord. We want to 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 the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return 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"]]

Example 4:

Input: products = ["havana"], searchWord = "tatiana"
Output: [[],[],[],[],[],[],[]]

 

Constraints:

• 1 <= products.length <= 1000
• There are no repeated elements in products.
• 1 <= Σ products[i].length <= 2 * 10^4
• All characters of products[i] are lower-case English letters.
• 1 <= searchWord.length <= 1000
• All characters of searchWord are lower-case English letters.

A:

锻炼了Trie 的写法。 

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        sort(products.begin(), products.end());
        buildTrie(products);
        vector<vector<string>> res;
        Trie* runner = root;
        for (char ch : searchWord) {
            vector<string> curLine;
            if(runner){
                runner = runner->children[ch - 'a'];
            }
            if (runner) { // if we found existing 
                for (int i = 0; i < min(3, (int)runner->words.size()); i++) {
                    curLine.push_back(runner->words[i]);
                }
            }
            res.push_back(curLine);
        }
        return res;
    }
private:
    struct Trie {
        vector<Trie*> children=vector<Trie*>(26, nullptr);//CANNOT use children(26,nullptr)
        vector<string> words;
    };
    Trie* root;
    void buildTrie(vector<string>& products) {
        root = new Trie();
        for (auto& word : products) {
            Trie* pre = root;
            for (char ch : word) {
                if (not pre->children[ch-'a']) {
                    pre->children[ch-'a'] = new Trie();
                }
                pre = pre->children[ch - 'a'];
                pre->words.push_back(word);
            }
        }
    }
};

Mistakes：

1： 很诡异地，出现了结果的前面为空，后面不为空的结果。TNND。 研究了大半个小时，发现是：

if（runner->childre[ch-'a'] )   这里的逻辑是：只有为不为空的时候，我们才往下走。 然而应该是已经为 runner 已经为nullptr 了。

所有应该是先往下指， 再看看是不是可以null。

我一开始把2个并到一起去了。