<p>You are given an array of strings <code>products</code> and a string <code>searchWord</code>.</p>

<p>Design a system that suggests at most three product names from <code>products</code> after each character of <code>searchWord</code> is typed. Suggested products should have common prefix with <code>searchWord</code>. If there are more than three products with a common prefix return the three lexicographically minimums products.</p>

<p>Return <em>a list of lists of the suggested products after each character of </em><code>searchWord</code><em> is typed</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> products = [&quot;mobile&quot;,&quot;mouse&quot;,&quot;moneypot&quot;,&quot;monitor&quot;,&quot;mousepad&quot;], searchWord = &quot;mouse&quot;
<strong>Output:</strong> [[&quot;mobile&quot;,&quot;moneypot&quot;,&quot;monitor&quot;],[&quot;mobile&quot;,&quot;moneypot&quot;,&quot;monitor&quot;],[&quot;mouse&quot;,&quot;mousepad&quot;],[&quot;mouse&quot;,&quot;mousepad&quot;],[&quot;mouse&quot;,&quot;mousepad&quot;]]
<strong>Explanation:</strong> products sorted lexicographically = [&quot;mobile&quot;,&quot;moneypot&quot;,&quot;monitor&quot;,&quot;mouse&quot;,&quot;mousepad&quot;].
After typing m and mo all products match and we show user [&quot;mobile&quot;,&quot;moneypot&quot;,&quot;monitor&quot;].
After typing mou, mous and mouse the system suggests [&quot;mouse&quot;,&quot;mousepad&quot;].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> products = [&quot;havana&quot;], searchWord = &quot;havana&quot;
<strong>Output:</strong> [[&quot;havana&quot;],[&quot;havana&quot;],[&quot;havana&quot;],[&quot;havana&quot;],[&quot;havana&quot;],[&quot;havana&quot;]]
<strong>Explanation:</strong> The only word &quot;havana&quot; will be always suggested while typing the search word.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= products.length &lt;= 1000</code></li>
	<li><code>1 &lt;= products[i].length &lt;= 3000</code></li>
	<li><code>1 &lt;= sum(products[i].length) &lt;= 2 * 10<sup>4</sup></code></li>
	<li>All the strings of <code>products</code> are <strong>unique</strong>.</li>
	<li><code>products[i]</code> consists of lowercase English letters.</li>
	<li><code>1 &lt;= searchWord.length &lt;= 1000</code></li>
	<li><code>searchWord</code> consists of lowercase English letters.</li>
</ul>

struct node {
    node (char let) : l(let), isEnd(false) {}
    char l;
    bool isEnd;
    std::vector<node*> ptrs;
};

class Solution {
public:
    Solution() {
        root = new node('\0');
    }

    std::vector<std::vector<std::string>> suggestedProducts(std::vector<std::string>& products, std::string searchWord) {
        int len = products.size(), lenWord = searchWord.length();
        std::string prefix = "";
        std::vector<std::vector<std::string>> vec;

        std::sort(products.begin(), products.end());

        // Вставляем все продукты в дерево
        for (int i = 0; i < len; ++i) {
            insert(products[i]);
        }

        // Для каждого префикса вызываем поиск
        for (int i = 0; i < lenWord; ++i) {
            prefix += searchWord[i];
            vec.push_back(search(prefix));
        }

        return vec;
    }

private:
    void insert(std::string word) {
        node* curr = root;

        for (char letter : word) {
            node* nextNode = nullptr;
            bool found = false;

            for (node* child : curr->ptrs) {
                if (child->l == letter) {
                    nextNode = child;
                    found = true;
                    break;
                }
            }

            if (!found) {
                nextNode = new node(letter);
                curr->ptrs.push_back(nextNode);
            }
            curr = nextNode;
        }
        curr->isEnd = true;
    }

    std::vector<std::string> search(std::string prefix) {
        node* curr = root;
        std::vector<std::string> pack;

        // Находим узел, соответствующий последнему символу префикса
        for (char letter : prefix) {
            bool found = false;
            for (node* child : curr->ptrs) {
                if (child->l == letter) {
                    curr = child;
                    found = true;
                    break;
                }
            }
            if (!found) return pack;  // Если префикс не найден, возвращаем пустой результат
        }

        // Собираем все слова, начиная с узла текущего префикса
        dfs(curr, prefix, pack);

        // Возвращаем максимум три слова
        if (pack.size() > 3) pack.resize(3);

        return pack;
    }

    void dfs(node* curr, std::string word, std::vector<std::string>& pack) {
        if (curr->isEnd) pack.push_back(word);
        if (pack.size() == 3) return; // Прерываем поиск, если нашли три слова

        for (node* child : curr->ptrs) {
            dfs(child, word + child->l, pack);
            if (pack.size() == 3) return;
        }
    }
    
    node* root;
};

489710