<p>Given an array of strings <code>nums</code> containing <code>n</code> <strong>unique</strong> binary strings each of length <code>n</code>, return <em>a binary string of length </em><code>n</code><em> that <strong>does not appear</strong> in </em><code>nums</code><em>. If there are multiple answers, you may return <strong>any</strong> of them</em>.</p>

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

<pre>
<strong>Input:</strong> nums = [&quot;01&quot;,&quot;10&quot;]
<strong>Output:</strong> &quot;11&quot;
<strong>Explanation:</strong> &quot;11&quot; does not appear in nums. &quot;00&quot; would also be correct.
</pre>

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

<pre>
<strong>Input:</strong> nums = [&quot;00&quot;,&quot;01&quot;]
<strong>Output:</strong> &quot;11&quot;
<strong>Explanation:</strong> &quot;11&quot; does not appear in nums. &quot;10&quot; would also be correct.
</pre>

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

<pre>
<strong>Input:</strong> nums = [&quot;111&quot;,&quot;011&quot;,&quot;001&quot;]
<strong>Output:</strong> &quot;101&quot;
<strong>Explanation:</strong> &quot;101&quot; does not appear in nums. &quot;000&quot;, &quot;010&quot;, &quot;100&quot;, and &quot;110&quot; would also be correct.
</pre>

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

<ul>
	<li><code>n == nums.length</code></li>
	<li><code>1 &lt;= n &lt;= 16</code></li>
	<li><code>nums[i].length == n</code></li>
	<li><code>nums[i] </code>is either <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
	<li>All the strings of <code>nums</code> are <strong>unique</strong>.</li>
</ul>

class TrieNode {
public:
    unordered_map<char, TrieNode*> next;

    ~TrieNode() {
        for (auto& [key, node] : next) delete(node);
    }
};

class Trie {
public:
    Trie() {
        root = new TrieNode();
    }

    void insert(string s) {
        TrieNode* node = root;
        for (auto& c : s) {
            if (node->next.count(c) == 0) node->next[c] = new TrieNode();
            node = node->next[c];
        }
    }

    string search(int length) {
        queue<pair<TrieNode*, string>> q;
        q.push({root, ""});
        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                auto [node, s] = q.front();
                q.pop();
                if (node->next.size() < keys.size()) {
                    // there is at least one key does not exists
                    for (auto& key : keys) {
                        if (node->next.count(key) != 0) continue;
                        return s + string(length - s.size(), key);
                    }
                }
                else {
                    // all keys exist, try all node
                    for (auto& [key, next_node] : node->next) {
                        q.push({next_node, s + string(1, key)});
                    }
                }
            }
        }
        return "";
    }
private:
    TrieNode* root;
    const vector<char> keys = {'0', '1'};
};

class Solution {
public:
    // time/space: O(n ^ 2)/O(n ^ 2)
    string findDifferentBinaryString(vector<string>& nums) {
        Trie trie;
        for (auto& num : nums) trie.insert(num);
        return trie.search(nums[0].size());
    }
};
20498