<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>

#include <cstddef>
#include <iostream>
#include <memory>
#include <map>
#include <optional>
#include <string>
#include <string_view>


class TrieNode
{
private:
    typedef std::map<char, std::unique_ptr<TrieNode>> children_t;
public:
    void insert(const std::string& word)
    {
        this->insert_(word);
    }

    void find(
        const std::size_t match_limit,
        const std::string_view& substring,
        std::vector<std::vector<string>>& output)
    {
        std::string matching;
        auto sub_iter = substring.cbegin();
        output.emplace_back();
        this->find_(match_limit, 0, substring, substring.cend(), sub_iter, matching, output);
    }
private:
    void insert_(const std::string_view& substring)
    {
        if (substring.empty())
        {
            //std::cout << "reached substring end" << std::endl;
            children_.emplace('\0', std::unique_ptr<TrieNode>());
            return;
        }
        auto sub_iter = substring.cbegin();
        std::optional<typename children_t::iterator> child = std::nullopt;
        if (this->children_.contains(*sub_iter))
        {
            //std::cout << "reusing=" << *sub_iter << std::endl;
            child.emplace(this->children_.find(*sub_iter));
            assert(child.value() != this->children_.end());
        }
        else
        {
            //std::cout << "inserting=" << *sub_iter << std::endl;
            const auto result = this->children_.emplace(*sub_iter, std::make_unique<TrieNode>());
            assert(result.second);
            child.emplace(result.first);
        }
        assert(child.has_value());
        ++sub_iter;
        std::string_view next(sub_iter, substring.end());
        child.value()->second->insert_(next);
    }

    std::size_t find_(
        const std::size_t match_limit,
        const std::size_t match_count,
        const std::string_view& substring,
        const std::string_view::iterator& sub_end,
        std::string_view::iterator& sub_iter,
        std::string current_match,
        std::vector<std::vector<string>>& output)
    {
        //std::cout << "match_limit=" << match_limit << ", match_count=" << match_count;
        if (match_count == match_limit)
        {
            //std::cout << ", limit reached" <<std::endl;
            return match_count;
        }
        std::size_t current_count = match_count;
        if (this->children_.contains('\0') && substring.size() <= current_match.size())
        {
            //std::cout << ", match=" << current_match;
            output.back().emplace_back(current_match);
            ++current_count;
            if (this->children_.size() == 1)
            {
                // reached a leaf in the trie
                //std::cout << ", reached leaf" <<std::endl;
                return current_count;
            }
        }
        if (sub_iter != sub_end && this->children_.contains(*sub_iter))
        {
            current_match.push_back(*sub_iter);
            auto& node_ptr = this->children_[*sub_iter];
            //std::cout << ", sub_iter=" << *sub_iter << ", current_match=" << current_match << std::endl;
            ++sub_iter;
            current_count = node_ptr->find_(match_limit, current_count, substring, sub_end, sub_iter, current_match, output);
            //std::cout << "backtracked to " << *sub_iter << ", count is now " << current_count << std::endl;
            current_match.pop_back();
        }
        else if (sub_iter == sub_end)
        {
            // we're already matching the requested substring, so any children from this node will match
            for (auto child_iter = this->children_.cbegin(); current_count < match_limit && child_iter != this->children_.cend(); ++child_iter)
            {
                if (child_iter->first == '\0')
                {
                    continue;
                }
                current_match.push_back(child_iter->first);
                //std::cout << ", current_match=" << current_match << std::endl;
                current_count = child_iter->second->find_(match_limit, current_count, substring, sub_end, sub_iter, current_match, output);
                //std::cout << "substring already matched, backtracked to " << child_iter->first << ", count is now " << current_count << std::endl;
                current_match.pop_back();
            }
        }
        return current_count;
    }

    children_t children_;
};


class Solution
{
public:
    std::vector<std::vector<std::string>> suggestedProducts(const vector<std::string>& products, const std::string& search_word)
    {
        //std::cout << "search_word=" << search_word << ", products=[" << std::endl;
        //for (const std::string& prod: products)
        //{
        //    std::cout << prod << std::endl;
        //}
        //std::cout << "]" << std::endl;
        TrieNode root;
        for (const string& prod: products)
        {
            root.insert(prod);
        }
        std::vector<std::vector<string>> suggestions;
        for (auto iter = search_word.cbegin(); iter != search_word.cend();)
        {
            ++iter;
            string_view substring(search_word.cbegin(), iter);
            root.find(3, substring, suggestions);
        }
        return suggestions;
    }
};
583070