题目描述
给你一个字符串数组 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.length1 <= n <= 16nums[i].length == nnums[i] 为 '0' 或 '1'nums 中的所有字符串 互不相同
解法
方法一：计数 + 枚举
由于 '1' 在长度为 \(n\) 的二进制字符串中出现的次数可以为 \(0, 1, 2, \cdots, n\)（共有 \(n + 1\) 种可能），因此我们一定可以找出一个新的二进制字符串，满足 '1' 在字符串中出现次数与 \(\textit{nums}\) 中每个字符串不同。
我们可以用一个整数 \(\textit{mask}\) 记录所有字符串中 '1' 出现次数的情况，即 \(\textit{mask}\) 的第 \(i\) 位为 \(1\) 表示长度为 \(n\) 的二进制字符串中 '1' 出现次数为 \(i\) 的字符串存在，否则不存在。
然后我们从 \(0\) 开始枚举长度为 \(n\) 的二进制字符串中 '1' 出现的次数 \(i\)，如果 \(\textit{mask}\) 的第 \(i\) 位为 \(0\)，则说明长度为 \(n\) 的二进制字符串中 '1' 出现次数为 \(i\) 的字符串不存在，我们可以将这个字符串作为答案返回。
时间复杂度 \(O(L)\)，其中 \(L\) 为 \(\textit{nums}\) 中字符串的总长度。空间复杂度 \(O(1)\)。
| class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
mask = 0
for x in nums:
mask |= 1 << x.count("1")
for i in count(0):
if mask >> i & 1 ^ 1:
return "1" * i + "0" * (len(nums) - i)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public String findDifferentBinaryString(String[] nums) {
int mask = 0;
for (var x : nums) {
int cnt = 0;
for (int i = 0; i < x.length(); ++i) {
if (x.charAt(i) == '1') {
++cnt;
}
}
mask |= 1 << cnt;
}
for (int i = 0;; ++i) {
if ((mask >> i & 1) == 0) {
return "1".repeat(i) + "0".repeat(nums.length - i);
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 | class Solution {
public:
string findDifferentBinaryString(vector<string>& nums) {
int mask = 0;
for (auto& x : nums) {
int cnt = count(x.begin(), x.end(), '1');
mask |= 1 << cnt;
}
for (int i = 0;; ++i) {
if (mask >> i & 1 ^ 1) {
return string(i, '1') + string(nums.size() - i, '0');
}
}
}
};
|
| func findDifferentBinaryString(nums []string) string {
mask := 0
for _, x := range nums {
mask |= 1 << strings.Count(x, "1")
}
for i := 0; ; i++ {
if mask>>i&1 == 0 {
return strings.Repeat("1", i) + strings.Repeat("0", len(nums)-i)
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12 | function findDifferentBinaryString(nums: string[]): string {
let mask = 0;
for (let x of nums) {
const cnt = x.split('').filter(c => c === '1').length;
mask |= 1 << cnt;
}
for (let i = 0; ; ++i) {
if (((mask >> i) & 1) === 0) {
return '1'.repeat(i) + '0'.repeat(nums.length - i);
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | /**
* @param {string[]} nums
* @return {string}
*/
var findDifferentBinaryString = function (nums) {
let mask = 0;
for (let x of nums) {
const cnt = x.split('').filter(c => c === '1').length;
mask |= 1 << cnt;
}
for (let i = 0; ; ++i) {
if (((mask >> i) & 1) === 0) {
return '1'.repeat(i) + '0'.repeat(nums.length - i);
}
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | public class Solution {
public string FindDifferentBinaryString(string[] nums) {
int mask = 0;
foreach (var x in nums) {
int cnt = x.Count(c => c == '1');
mask |= 1 << cnt;
}
int i = 0;
while ((mask >> i & 1) == 1) {
i++;
}
return string.Format("{0}{1}", new string('1', i), new string('0', nums.Length - i));
}
}
|
方法二：构造
我们可以构造一个长度为 \(n\) 的二进制字符串 \(\textit{ans}\)，其中 \(\textit{ans}\) 的第 \(i\) 位与 \(\textit{nums}[i]\) 的第 \(i\) 位不同。由于 \(\textit{nums}\) 中的字符串互不相同，因此 \(\textit{ans}\) 不会出现在 \(\textit{nums}\) 中。
时间复杂度 \(O(n)\)，其中 \(n\) 是 \(\textit{nums}\) 中字符串的长度。忽略答案字符串的空间复杂度，空间复杂度 \(O(1)\)。