<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 <utility>
#include <algorithm>
#include <deque>
/*
1. each Trie node could contain more info: not only next char, but also the number of strings of the next char (so that we can decide how many words we need to fetch)
If no such info, we would: while count is < 3, go to smallest next char, fetch word; Then go back up if no more words;
2. Design of Trie Node:
struct Node
{
    char ch;
    bool isEnd;
    vecotr<pair<Node*, word_count>> next;
    int word_count; // including current char
};
3. On an input:
(a) we go to Trie and follow the nodes
(b) track how many word_count we have at the last char
(c) if word_count >= 3, decide how to distribute:
c.1 if isEnd, then current word is selected; 3 --;
c.2 use a helper to collect words up to 3. 
c.3 concat input + words and return
4. overall logic:
(a) build a Trie
(b) search
*/
class Solution {
public:
    struct Node {
        char ch;
        bool isEnd;
        vector<pair<Node*, int> > next; // <Node*, wordCount> of next chars
        int wordCount;

        Node(char ch, bool isEnd = false)
        : ch(ch), isEnd(isEnd), next(26, make_pair(nullptr, 0)), wordCount(0) // wordCount init to 0, will update on next char insertion
        {}
    };

    // for debug use, print Trie in BFS way
    void printTrie(Node* root) {
        if(!root) {
            cout << "Trie is empty\n";
            return;
        }
        deque<pair<Node*, string> > bfs;
        bfs.push_front(make_pair(root, ""));
        size_t indent = 0;
        while(bfs.size() > 0) {
            // for each level
            cout << string(indent, ' ') << "[ ";
            size_t count = bfs.size();
            for(size_t i = 0; i < count; ++i){ // for each bfs element
                auto& last_element = bfs.back();
                auto [node, word] = last_element;
                bfs.pop_back();
                //auto [node, word] = bfs.pop_back();
                cout << word << ", ";
                for(size_t j = 0; j < 26; ++j) {
                    if(node->next[j].first) { // has next char
                        string next_word = word + (char)('a' + j);
                        bfs.push_front(make_pair(node->next[j].first, next_word));
                    }
                }
            }
            cout << "]\n";
            indent += 2;
        }
        cout << endl;
    }


    Node* buildTrie(vector<string>& products) {
        Node* root = new Node(' ', false); // init
        //root->wordCount = 0; // root is special; reset wordCount to 0 at init
        for(string product : products) {
            Node* insert_ptr = root;
            for(auto ch : product) {            
                insert_ptr->wordCount ++;
                size_t pos = ch - 'a';
                insert_ptr->next[pos].second ++; // wordCount ++
                if(!insert_ptr->next[pos].first) { // next char Node do not exist
                    insert_ptr->next[pos].first = new Node(ch, false); // creat Node
                }
                insert_ptr = insert_ptr->next[pos].first; // move ptr to next char
            }
            // handle last char
            insert_ptr->isEnd = true;
            insert_ptr->wordCount ++;
        }
        return root;
    }

    void updateHelper(Node* root, string& searchWord, vector<string>& suggestion, int return_count) {
        // base case
        if(return_count <= 0) {
            return; // do nothing
        }
        int count = return_count;
        if(root->isEnd) { // use current word
            suggestion.push_back(searchWord);
            count --;
        }
        size_t pos = 0;
        while(pos < 26 && count > 0) { // backtrack
            int next_count = min(root->next[pos].second, count); // how many words we can fetch from next char
            if(next_count > 0){
                searchWord += ('a' + pos); // append next char
                updateHelper(root->next[pos].first, searchWord, suggestion, count); // recursion
                searchWord.pop_back(); // reset searchWord
                count -= next_count;
            }
            pos ++; // next iter
        }
        return;
    }

    // return current Node* for next search
    Node* updateSuggestion(Node* root, string& searchWord, char ch, vector<string>& suggestion) {
        //cout << "search " << searchWord << ", ch " << ch << " at root " << root << endl;

        // base case
        if(!root) {
            return root; // do nothing
        }
        size_t pos = ch - 'a';
        Node* ch_root = root->next[pos].first;
        if(!ch_root) { // can not find this char, break
            //cout << "  no ch_root ptr found!" << endl;
            auto next_ch = root->next[pos];
            //cout << "  pos: " << pos << ", next word count " << next_ch.second << endl;
            return ch_root;
        }
        int return_count = min(3, ch_root->wordCount); // set how many return strings we can return; max is 3
        //cout << "  return_count " << return_count << endl;
        // use a recursive helper function to find remaining words
        updateHelper(ch_root, searchWord, suggestion, return_count);
        //cout << "  return ch_root " << ch_root << endl;
        return ch_root;
    }

    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {
        Node* root = buildTrie(products);
        //printTrie(root);
        // iterate on each step of searchWord
        vector<vector<string> > vec_output;
        string str_search = "";
        Node* search_root = root;
        for(auto ch : searchWord) {
            str_search += ch;
            vector<string> suggestion;
            // search
            search_root = updateSuggestion(search_root, str_search, ch, suggestion); // update search root to current char
            vec_output.push_back(vector<string>(suggestion)); // use copy constructor to copy suggestion
        }
        return vec_output;
    }
};
116270