struct node {
    node* arr[26] = {nullptr};
    bool flag = false;
    vector<string> below;
    bool contains(char ch) {
        if (arr[ch - 'a']) return true;
        else return false;
    }
    void add(char ch, node* sub) {
        arr[ch - 'a'] = sub;
    }
    node* next(char ch) {
        return arr[ch - 'a'];
    }
    void end() {
        flag = true;
    }
    bool isend() {
        return flag;
    }
    void ins(string bel) {
        below.push_back(bel);
    }
    void put(vector<string>& res) {
        int count = 0;
        for (auto it : below) {
            res.push_back(it);
            if (++count == 3) break;
        }
    }
};

class Trie {
private:
    node* root = new node();
public:
    void insert(string word) {
        node* nod = root;
        for (int i = 0; i < word.length(); ++i) {
            if (!nod->contains(word[i])) {
                nod->add(word[i], new node()); 
            }
            nod = nod->next(word[i]);
            nod->ins(word);
        }
        nod->end();
    }

    vector<vector<string>> search(string word) {
        vector<vector<string>> res;
        node* nod = root;
        for (int i = 0; i < word.length(); ++i) {
            vector<string> ans;
            if (!nod->contains(word[i])) {
                break;
            }
            nod = nod->next(word[i]);
            nod->put(ans);
            res.push_back(ans);
        }
        while (res.size() < word.size()) {
            res.push_back({});
        }
        return res;
    }
};

class Solution {
public:
    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        sort(products.begin(), products.end());
        Trie a;
        for (auto it : products) {
            a.insert(it);
        }
        return a.search(searchWord);
    }
};