<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:
    typedef struct trie{
        int use;
        bool end;
        vector<struct trie> v;
    } Trie;

    static bool cmp(string &a, string &b) {
        if (a.size() == b.size())
            return a < b;
        return a.size() < b.size();
    }

    bool insert(Trie *r, string s){
        for(int i = 0; i < s.size() - 1; i++) {
            if (r->v[s[i] - 'a'].use) {
                r = &r->v[s[i] - 'a'];
            } else {
                return false;
            }
        }
        if (r->end) {

            r->v[s[s.size() - 1] - 'a'].use = 1;
            r->v[s[s.size() - 1] - 'a'].end = true;
            r->v[s[s.size() - 1] - 'a'].v.resize(26);
            for(int i = 0; i < 26; i++) {
                r->v[s[s.size() - 1] - 'a'].v[i].use = 0;
                r->v[s[s.size() - 1] - 'a'].v[i].end = 0;
            }
            return true;
        }
        return false;
    }
    string longestWord(vector<string>& w) {
        Trie root;
        root.use = 1;
        root.end = true;
        root.v.resize(26);
        for(int i = 0; i < 26; i++) {
            root.v[i].use = 0;
            root.v[i].end = 0;
        }
        string ans = "";
        int curlen = 0;

        sort(w.begin(), w.end(), cmp);

        for(int i = 0; i < w.size(); i++) {
            cout<<w[i]<<" ";
            if (w[i].size() - curlen > 1) return ans;

            if (insert(&root, w[i])) {
                cout<<w[i]<<" ";
                if (w[i].size() - curlen == 1) {
                    ans = w[i];
                    curlen = w[i].size();
                }
            }
        }
        cout<<"\n";
        return ans;
    }
};
42534