<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) -> None:
#         self.children = defaultdict(TrieNode)
#         self.word_set = set()

# class Trie:
#     def __init__(self) -> None:
#         self.root = TrieNode()

#     def insert(self, word, idx) -> None:
#         n = len(word)
#         for i in range(n):
#             node = self.root
#             for char in word[i:]:
#                 if char not in node.children:
#                     node.children[char] = TrieNode()
#                 node = node.children[char]
#                 node.word_set.add(idx)

#     def find(self, word):
#         n = len(word)
#         res = []
#         for i in range(n):
#             node = self.root
#             cur_str = ''
#             for char in word[i:]:
#                 cur_str += char
#                 node = node.children[char]
#                 if len(node.word_set) == 1:
#                     res.append(cur_str)
#                     break
#         return sorted(res, key=lambda x: (len(x), x))[0] if res else ''

class Solution:
#     def shortestSubstrings(self, arr: List[str]) -> List[str]:
#         t = Trie()
#         for idx, word in enumerate(arr):
#             t.insert(word, idx)
#         res = []
#         for word in arr:
#             res.append(t.find(word))
#         return res

    def shortestSubstrings(self, arr: List[str]) -> List[str]:
        res = []
        for i in range(len(arr)):
            resSub = '{zzzzzzzzzzzzzzzzzzz'
            for j in range(len(arr[i])):
                for k in range(j, len(arr[i])):
                    sub = arr[i][j:k+1]
                    flg = True
                    for wd in range(len(arr)):
                        if wd == i:
                            continue 
                        if sub in arr[wd]:
                            flg = False
                            break
                    if len(sub) <= len(resSub) and flg == True:
                        if sub < resSub or len(sub) < len(resSub):
                            resSub = sub
            if resSub == '{zzzzzzzzzzzzzzzzzzz':
                resSub = ''
            res.append(resSub)
        return res
829