<p>You are given an array <code>arr</code> of size <code>n</code> consisting of <strong>non-empty</strong> strings.</p>

<p>Find a string array <code>answer</code> of size <code>n</code> such that:</p>

<ul>
	<li><code>answer[i]</code> is the <strong>shortest</strong> <span data-keyword="substring">substring</span> of <code>arr[i]</code> that does <strong>not</strong> occur as a substring in any other string in <code>arr</code>. If multiple such substrings exist, <code>answer[i]</code> should be the <span data-keyword="lexicographically-smaller-string">lexicographically smallest</span>. And if no such substring exists, <code>answer[i]</code> should be an empty string.</li>
</ul>

<p>Return <em>the array </em><code>answer</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr = [&quot;cab&quot;,&quot;ad&quot;,&quot;bad&quot;,&quot;c&quot;]
<strong>Output:</strong> [&quot;ab&quot;,&quot;&quot;,&quot;ba&quot;,&quot;&quot;]
<strong>Explanation:</strong> We have the following:
- For the string &quot;cab&quot;, the shortest substring that does not occur in any other string is either &quot;ca&quot; or &quot;ab&quot;, we choose the lexicographically smaller substring, which is &quot;ab&quot;.
- For the string &quot;ad&quot;, there is no substring that does not occur in any other string.
- For the string &quot;bad&quot;, the shortest substring that does not occur in any other string is &quot;ba&quot;.
- For the string &quot;c&quot;, there is no substring that does not occur in any other string.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr = [&quot;abc&quot;,&quot;bcd&quot;,&quot;abcd&quot;]
<strong>Output:</strong> [&quot;&quot;,&quot;&quot;,&quot;abcd&quot;]
<strong>Explanation:</strong> We have the following:
- For the string &quot;abc&quot;, there is no substring that does not occur in any other string.
- For the string &quot;bcd&quot;, there is no substring that does not occur in any other string.
- For the string &quot;abcd&quot;, the shortest substring that does not occur in any other string is &quot;abcd&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == arr.length</code></li>
	<li><code>2 &lt;= n &lt;= 100</code></li>
	<li><code>1 &lt;= arr[i].length &lt;= 20</code></li>
	<li><code>arr[i]</code> consists only of lowercase English letters.</li>
</ul>

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = {}

class Trie:

    def __init__(self):
        self.root = TrieNode()
        
    def insert(self, word: str, id: int) -> None:
        node = self.root
        for ch in word:
            if not ch in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_end[id] = 1

    def search(self, word: str) -> bool:
        node = self.root
        for ch in word:
            if not ch in node.children:
                return False
            node = node.children[ch]
        #print(word, len(node.is_end))
        return len(node.is_end) == 1

class Solution:
    def shortestSubstrings(self, arr: List[str]) -> List[str]:
        trie = Trie()
        for id in range(len(arr)):
            for d in range(len(arr[id])):
                for r in range(d, len(arr[id])):
                    l = r - d
                    trie.insert(arr[id][l:r + 1], id) 
        ans = []

        for word in arr:
            min_sub = '~' * (len(word))
            for d in range(len(word)):
                for r in range(d, len(word)):
                    l = r - d
                    if trie.search(word[l:r + 1]):
                        if len(min_sub) < d + 1:
                            pass
                        elif len(min_sub) == d + 1:
                            min_sub = min(min_sub, word[l:r + 1])
                        else:
                            min_sub = word[l:r + 1]

            if min_sub == '~' * (len(word)):
                min_sub = ''
            ans.append(min_sub)

        return ans

        
556