1980. 找出不同的二进制字符串

English Version

题目描述

给你一个字符串数组 nums ，该数组由 n 个 互不相同 的二进制字符串组成，且每个字符串长度都是 n 。请你找出并返回一个长度为 n 且 没有出现 在 nums 中的二进制字符串。如果存在多种答案，只需返回 任意一个 即可。

 

示例 1：

输入：nums = ["01","10"]
输出："11"
解释："11" 没有出现在 nums 中。"00" 也是正确答案。

示例 2：

输入：nums = ["00","01"]
输出："11"
解释："11" 没有出现在 nums 中。"10" 也是正确答案。

示例 3：

输入：nums = ["111","011","001"]
输出："101"
解释："101" 没有出现在 nums 中。"000"、"010"、"100"、"110" 也是正确答案。

 

提示：

• n == nums.length
• 1 <= n <= 16
• nums[i].length == n
• nums[i] 为 '0' 或 '1'
• nums 中的所有字符串 互不相同

解法

"1" 在长度为 n 的二进制字符串中出现的次数可为 0, 1, 2, ..., n （共有 n + 1 种可能）。

由于 nums 的长度为 n (n 种可能)，因此我们一定可以找出一个新的二进制字符串，满足 "1" 在字符串中出现次数与 nums 中每个字符串不同。

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 ""
}

...