<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:
     string ans;
    static bool comp (const string&a,const string &b){
        return (int)(a.size())<(int)(b.size());
    }
    struct trie{
        trie* next[26];
        bool end;
    };
    trie *getNode(){
        trie *curr=new trie();
        for(int i=0;i<26;i++)
        curr->next[i]=NULL;
        curr->end=false;
        return curr;
    }
    void insert(trie * root,string &s){
      trie *curr=root;
      bool last=true;
      int n=s.size();
      for(int i=0;i<n;i++){
        int x=s[i]-'a';
        if(curr->next[x]){
        curr=curr->next[x];
        }
        else{
            curr->next[x]=getNode();
            curr=curr->next[x];
        }
        if(i==n-1){
        curr->end=true;
        }
        last=last && (curr->end);
        if(last && i==n-1){
            int slen=n;
            int anslen=ans.size();
            if(slen>=anslen){
                if(slen==anslen && (s<ans))
                ans=s;
                if(slen>anslen)
                ans=s;

            }
        }
        if(!last)
        return ;
      }
      curr->end=true;

    }

    string longestWord(vector<string>& words) {
        sort(words.begin(),words.end(),comp);
       
        ans="";
        trie* root=getNode();
        for(auto it:words)
        insert(root,it);

        return ans;
    }
};
26065