<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:
            char val;
            vector<TrieNode*> children;
            bool isTerminal;
            int endCount, prefixCount, childCount;

            TrieNode(int val){
                this->val = val;
                this->isTerminal = false;
                children.resize(26);
                this->endCount = 0;
                this->prefixCount = 0;
                this->childCount = 0;

                for (int i = 0; i < 26; i++){
                    children[i] = nullptr;
                }
            }
    };

    class Trie{
        public:
            TrieNode* root;

            Trie(){
                root = new TrieNode('a');
            }

            TrieNode* fetchNode(){
                return root;
            }

            void insertUtil(TrieNode* &root, string str){
                TrieNode* temp = root;
                for (int i = 0; i < str.length(); i++){
                    int index = str[i] - 'a';
                    if (temp->children[index] == nullptr){
                        temp->children[index] = new TrieNode(str[i]);
                        temp->childCount++;
                    }

                    temp->prefixCount++;
                    temp = temp->children[index];
                }

                temp->isTerminal = true;
                temp->endCount++;
            }

            void insertWord(string str){
                insertUtil(root, str);
            }
    };

    bool completeStringUtil(TrieNode* root, string str){
        TrieNode* temp = root;
        int n = str.length();

        for (int i = 0; i < n; i++){
            int index = str[i] - 'a';

            if (temp->children[index] != nullptr){
                temp = temp->children[index];
                if (temp->isTerminal == false){
                    return false;
                }
            }
            else{
                return false;
            }
        }
        return true;
    }

    string longestWord(vector<string>& arr) {
        int n = arr.size();
        Trie* t = new Trie();

        for (int i = 0; i < n; i++){
            string str = arr[i];
            t->insertWord(str);
        }

        TrieNode* root = t->fetchNode();
        int maxLen = 0;
        string complete_string = "";

        for (int i = 0; i < n; i++){
            string str = arr[i];
            if (completeStringUtil(root, str) == true){
                if (str.length() > maxLen){
                    maxLen = str.length();
                    complete_string = str;
                }
                else if (str.length() == maxLen && str < complete_string){
                    complete_string = str;
                }
            }
        }

        return complete_string;
    }
};
40940