<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 Trie{
public:
    Trie* v[26];
    int freq;
    bool endMark;
    Trie(){
        freq=0;
        for (int i=0; i<26; i++){
            v[i]=NULL;
        }
        endMark=false;
    }

    void insert(string word) {
        int l=word.length();
        Trie * tmp = this;
        for (int i=0; i<l; i++){
            if (tmp->v[word[i]-'a']==NULL){
                tmp->v[word[i]-'a']=new Trie();
            }
            tmp = tmp->v[word[i]-'a'];
            // tmp->freq++;
        }
        tmp->endMark=true;
    }

    bool search(string word) {
        int l=word.length();
        Trie * tmp = this;
        for (int i=0; i<l; i++){
            if (tmp->v[word[i]-'a']==NULL) return false;
            tmp = tmp->v[word[i]-'a'];
        }

        return tmp->endMark;
    }
};

class Solution {
public:
    string longestWord(vector<string>& words) {
        int mx = 0;
        int n = words.size();
        Trie* t = new Trie();
        for (int i=0; i<n; i++){
            t->insert(words[i]);
        }
        vector<string> ans;
        for (int i=0; i<n; i++){
            int l = words[i].length();
            string pref = "";
            bool poss=true;
            for (int j=0; j<l; j++){
                pref+=words[i][j];
                // cout<<pref<<'\n';
                if (!(t->search(pref))){
                    poss=false;
                    break;
                }
            }
            if (poss){
                mx = max(mx, l);
                ans.push_back(words[i]);
            }
        }

        sort(ans.begin(), ans.end());

        string res;
        for (int i=0; i<(int)ans.size(); i++){
            if (ans[i].length()==mx){
                res=ans[i];
                break; 
            }
        }
        return res;
    }
};
51565