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

struct Node{
    Node* links[26];
    bool flag = false;

    bool containsKey(char ch){
		return links[ch-'a']!=NULL;
	}

    Node *get(char ch){
		return links[ch-'a'];
	}

    void put(char ch,Node *node){
		links[ch-'a']=node;
	}

    void setEnd(){
		flag=true;
	}
	bool isEnd(){
		return flag;
	}
};

class Trie{
    private: Node *root;

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

        void insert(string word) {
            Node *node=root;
            for(int i=0;i<word.size();i++){
                if(!node->containsKey(word[i])){
                    node->put(word[i],new Node());
                }
                node=node->get(word[i]);
            }
            node->setEnd();
        }

        bool checkIfPrefixExist(string word){
            Node* node = root;
            for(auto ch:word){
                if(node->containsKey(ch)){
                    node=node->get(ch);
                    if(node->isEnd()==false) return false;
                }
                else return false;
            }
            return true;
        }
};

class Solution {
public:
    string longestWord(vector<string>& a) {
        Trie trie;

        for(auto &it : a){
            trie.insert(it);
        }

        string longest = "";

        for(auto it : a){
            if(trie.checkIfPrefixExist(it)){
                if(it.length() > longest.length()){
                    longest = it;
                }
                else if(it.length() == longest.length() && it < longest){
                    longest = it;
                }
            }
        }

        return longest;
    }
};
35628