[Leetcode] 1980. Find Unique Binary String

1980. Find Unique Binary String

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

Constraints:

n == nums.length

1 <= n <= 16

nums[i].length == n

nums[i] is either '0' or '1'.

Analysis:

In order to reduce the time complexity, we need to,

1. store the existing strings in a unordered_set, which makes the checking in O(1);

2. save the visited string, to avoid infinite loop;

Then we can start with the first string, and try to flip each char, until we can find a brand new string.

See the code below:

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        int n = nums.size();
        unordered_set<string> st;
        for(auto &a : nums) st.insert(a);
        unordered_set<string> vis;
        string res = nums[0];
        while(st.count(res) > 0) {
            for(int i=0; i<n; ++i) {
                res[i] = res[i] ^ 1;
                if(vis.count(res)) continue;
                vis.insert(res);
                if(st.count(res)) break;
                return res;
            }
        }
        return res;
    }
};