<p>Given an array of strings <code>words</code> representing an English Dictionary, return <em>the longest word in</em> <code>words</code> <em>that can be built one character at a time by other words in</em> <code>words</code>.</p>

<p>If there is more than one possible answer, return the longest word with the smallest lexicographical order. If there is no answer, return the empty string.</p>

<p>Note that the word should be built from left to right with each additional character being added to the end of a previous word.&nbsp;</p>

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

<pre>
<strong>Input:</strong> words = [&quot;w&quot;,&quot;wo&quot;,&quot;wor&quot;,&quot;worl&quot;,&quot;world&quot;]
<strong>Output:</strong> &quot;world&quot;
<strong>Explanation:</strong> The word &quot;world&quot; can be built one character at a time by &quot;w&quot;, &quot;wo&quot;, &quot;wor&quot;, and &quot;worl&quot;.
</pre>

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

<pre>
<strong>Input:</strong> words = [&quot;a&quot;,&quot;banana&quot;,&quot;app&quot;,&quot;appl&quot;,&quot;ap&quot;,&quot;apply&quot;,&quot;apple&quot;]
<strong>Output:</strong> &quot;apple&quot;
<strong>Explanation:</strong> Both &quot;apply&quot; and &quot;apple&quot; can be built from other words in the dictionary. However, &quot;apple&quot; is lexicographically smaller than &quot;apply&quot;.
</pre>

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

<ul>
	<li><code>1 &lt;= words.length &lt;= 1000</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 30</code></li>
	<li><code>words[i]</code> consists of lowercase English letters.</li>
</ul>

class Solution {
public:
    /*
        #Approach #1: Ues trie and maintain word in each node and search if node has word.

        #Approach #2: Use map and keep insert words,
    */

    static bool comp(string s, string t) {  // sorting comparator
        return s.size() < t.size();
    }

    string longestWord(vector<string>& words) {
        sort(words.begin(), words.end(), comp);  // sort words by non-decreasing length
        unordered_map<string, bool> goodWords;        // lookup for good words
        int maxLength = 0;
        string ans = "";
        for (string word : words) {
            if (word.size() == 1) {
                goodWords[word] = true;
            } else if (goodWords[word.substr(0, word.size() - 1)]) {  // word with length - 1 prefix is good
                goodWords[word] = true;
            }
            
            if (goodWords[word]) {
                if (maxLength < word.size()) {  // find longer word
                    maxLength = word.size();
                    ans = word;
                } else if (maxLength == word.size()) {  // find lexicographically smaller word
                    ans = min(ans, word);
                }
            }
        }
        return ans;
    }


    // typedef struct node
    // {
    //     string word;
    //     map<char, struct node*> child;
    // }Trie;

    // Trie* createNode()
    // {
    //     Trie* nn = new Trie();
    //     nn->word = "";
    //     return nn;
    // }

    // void findLargestWord(Trie* node, string &result)
    // {
    //     if(node == nullptr) return;

    //     Trie* trav = node;
    //     for(auto it = trav->child.begin(); it != trav->child.end(); it++)
    //     {
    //         char ch = it->first;
    //         Trie* ptr = it->second;
    //         string str = ptr->word;
    //         cout<< "str: "<< str << endl;
    //         if(str != "")
    //         {
    //             if(str.length() > result.length())
    //             {
    //                 result = str;
    //             }
                
    //             findLargestWord(ptr, result);
    //         }
    //     }
    // }

    // void insert(string &word)
    // {
    //     Trie* trav = root;
    //     for(auto ch:word)
    //     {
    //         if(trav->child[ch] == nullptr)
    //             trav->child[ch] = createNode();
            
    //         trav = trav->child[ch];
    //     }
    //     trav->word = word;
    // }

    // void insertNode(vector<string>& words)
    // {
    //     for(auto word:words)
    //     {
    //         insert(word);
    //     }
    // }

    

    // string longestWord(vector<string>& words) {
    //     // insert all nodes
    //     insertNode(words);

    //     // search for the nodes
    //     string result = "";
    //     findLargestWord(root, result);
    //     return result;
    // }

    // Trie* root = createNode();
};
43065