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

    class TrieNode {
    public:
        TrieNode* children[26];
        bool isEndOfWord;
        TrieNode() {
            for (int i = 0; i < 26; ++i) children[i] = nullptr;
            isEndOfWord = false;
        }
    };
    
    class Trie {
    private:
        TrieNode* root;
        
        TrieNode* searchNode(const string& prefix) {
            TrieNode* node = root;
            for (char c : prefix) {
                int index = c - 'a';
                if (!node->children[index]) return nullptr;
                node = node->children[index];
            }
            return node;
        }

        void collectWords(TrieNode* node, string prefix, vector<string>& words) {
            if (!node) return;
            if (node->isEndOfWord) {
                words.push_back(prefix);
            }
            for (int i = 0; i < 26; ++i) {
                if (node->children[i]) {
                collectWords(node->children[i], prefix + char(i + 'a'), words);
                }
            }
        }

        void makesol(TrieNode* root, string& sol, string tmp, bool isFirst) {
        if (root==NULL)
        {
            return;
        }
        if (root->isEndOfWord==0&&isFirst==0)
        return;
        for (int i=0;i<26;i++)
        {
                char s=i+'a';
                makesol(root->children[i],sol, tmp+s,0);
        }
        if (tmp.length()>sol.length())
                sol=tmp;
        }

    public:
        Trie() {
            root = new TrieNode();
        }

        string sol()
        {
            string solu="";
            string tmp="";
            makesol(root,solu,tmp,1);
            return solu;
        }

        void insert(const string& word) {
            TrieNode* node = root;
            for (char c : word) {
                int index = c - 'a';
                if (!node->children[index]) {
                    node->children[index] = new TrieNode();
                }
                node = node->children[index];
            }
            node->isEndOfWord = true;
        }

        vector<string> prefixSearch(const string& prefix) {
            vector<string> words;
            TrieNode* node = searchNode(prefix);
            if (node) {
                collectWords(node, prefix, words);
            }
            return words;
        }
    };

    string longestWord(vector<string>& words) {
        Trie root;
        for (int i=0;i<words.size();i++)
        {
            root.insert(words[i]);
        }
        return root.sol();
    }
};
56346