README_EN.md

1980. Find Unique Binary String

中文文档

Description

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.

 

Example 1:

Input: nums = ["01","10"]
Output: "11"
Explanation: "11" does not appear in nums. "00" would also be correct.

Example 2:

Input: nums = ["00","01"]
Output: "11"
Explanation: "11" does not appear in nums. "10" would also be correct.

Example 3:

Input: nums = ["111","011","001"]
Output: "101"
Explanation: "101" does not appear in nums. "000", "010", "100", and "110" would also be correct.

 

Constraints:

• n == nums.length
• 1 <= n <= 16
• nums[i].length == n
• nums[i] is either '0' or '1'.
• All the strings of nums are unique.

Solutions

Python3

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        s = set(num.count("1") for num in nums)
        n = len(nums)
        for i in range(n + 1):
            if i not in s:
                return "1" * i + "0" * (n - i)
        return ""

Java

class Solution {
    public String findDifferentBinaryString(String[] nums) {
        Set<Integer> s = count(nums);
        int n = nums.length;
        for (int i = 0; i < n + 1; ++i) {
            if (!s.contains(i)) {
                return "1".repeat(i) + "0".repeat(n - i);
            }
        }
        return "";
    }

    private Set<Integer> count(String[] nums) {
        Set<Integer> s = new HashSet<>();
        for (String num : nums) {
            int t = 0;
            for (char c : num.toCharArray()) {
                if (c == '1') {
                    ++t;
                }
            }
            s.add(t);
        }
        return s;
    }
}

C++

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        auto s = count(nums);
        for (int i = 0, n = nums.size(); i < n + 1; ++i) {
            if (!s.count(i))
                return repeat("1", i) + repeat("0", n - i);
        }
        return "";
    }

    unordered_set<int> count(vector<string>& nums) {
        unordered_set<int> s;
        for (auto& num : nums) {
            int t = 0;
            for (char c : num) {
                if (c == '1')
                    ++t;
            }
            s.insert(t);
        }
        return s;
    }

    string repeat(string s, int n) {
        string res = "";
        for (int i = 0; i < n; ++i) {
            res += s;
        }
        return res;
    }
};

Go

func findDifferentBinaryString(nums []string) string {
	count := func() []bool {
		s := make([]bool, 17)
		for _, num := range nums {
			t := 0
			for _, c := range num {
				if c == '1' {
					t++
				}
			}
			s[t] = true
		}
		return s
	}
	s := count()
	for i, n := 0, len(nums); i <= n; i++ {
		if !s[i] {
			return strings.Repeat("1", i) + strings.Repeat("0", n-i)
		}
	}
	return ""
}

...