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

from collections import defaultdict
class TrieNode:
    def __init__(self, end_of_word = False, children = None):
        self.end_of_word = end_of_word
        self.children = {} if children is None else children

    def insert(self, word):
        curr_node = self
        for char in word:
            if char not in curr_node.children:
                curr_node.children[char] = TrieNode()
            curr_node = curr_node.children[char]

        # end of word
        curr_node.end_of_word = True

    def search(self, word):
        result = []
        curr_node = self
        for char in word:
            print()
            if char in curr_node.children:
                result.append(char)
                curr_node = curr_node.children[char]
            else:
                break
        print(curr_node.children.keys())
        print(f"word: {word}, result: {result}, end_of_word: {curr_node.end_of_word}")
        return "".join(result) if curr_node.end_of_word else ""

class Solution:
    def longestWord(self, words: List[str]) -> str:
        words.sort()

        head_of_trie = TrieNode()

        result = ""

        for word in words:
            matching_prefix = head_of_trie.search(word)
            if len(word) - len(matching_prefix) == 1:
                head_of_trie.insert(word)
                if len(word) > len(result):
                    result = word


        return result
17300