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

🟠   🔖  数组 哈希表 字符串 回溯  🔗 力扣 LeetCode

题目

Given an array of strings nums containing n unique binary strings each of length n, return a binary string of lengthn _thatdoes not appear in _nums . If there are multiple answers, you may returnany 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.

题目大意

给你一个字符串数组 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 中的所有字符串 互不相同

解题思路

思路一：回溯

回溯法用于枚举所有可能的 n 位二进制字符串，并找到一个不在 nums 中的字符串。

1. 使用 Set 记录已存在的二进制字符串

   • 由于 nums 中的二进制字符串都是唯一的，可以用 Set 进行快速查找。

2. 使用递归构造所有可能的 n 位二进制字符串

   • 递归构造每一位，可以选择 0 或 1，形成一个树形递归结构。
   • 当构造出一个长度为 n 的字符串时，检查它是否在 Set 中，如果不在，则记录为结果并返回。

3. 终止条件

   • 当找到一个不在 nums 中的字符串时，立即终止回溯，返回该字符串。

复杂度分析

• 时间复杂度：O(2^n)，最坏情况下需要遍历所有 n 位二进制字符串。
• 空间复杂度：O(n)，递归调用栈的最大深度为 n。

---

思路二：对角线法

对角线法是一种巧妙的构造方法，能够在 O(n) 时间复杂度内找到一个不在 nums 中的字符串。

1. 利用对角线特性生成唯一字符串
2. 依次遍历 nums 的第 i 个字符串，取它的第 i 位并翻转（即 0 变 1，1 变 0）。
3. 这样形成的新字符串一定与 nums 中的所有字符串至少有一位不同，因此不会出现在 nums 里。

复杂度分析

• 时间复杂度：O(n)，只需遍历 nums 一次即可构造出一个新的字符串。
• 空间复杂度：O(n)，用于存储最终生成的字符串。

---

代码

回溯

/**
 * @param {string[]} nums
 * @return {string}
 */
var findDifferentBinaryString = function (nums) {
	const n = nums.length;
	const exists = new Set(nums);
	let result = null;
	const backtrack = (track) => {
		if (result !== null) {
			return result;
		}
		if (track.length == n) {
			if (!exists.has(track.join(''))) {
				result = track.join('');
			}
			return;
		}
		for (let char of ['0', '1']) {
			track.push(char);
			backtrack(track);
			track.pop();
		}
	};
	backtrack([]);
	return result;
};

对角线法

/**
 * @param {string[]} nums
 * @return {string}
 */
var findDifferentBinaryString = function (nums) {
	let n = nums.length;
	let result = '';
	for (let i = 0; i < n; i++) {
		result += nums[i][i] === '0' ? '1' : '0';
	}
	return result;
};

相关题目

题号	标题	题解	标签	难度	力扣
268	丢失的数字	[✓]	位运算 数组 哈希表 3+	🟢	🀄️ 🔗
448	找到所有数组中消失的数字	[✓]	数组 哈希表	🟢	🀄️ 🔗
710	黑名单中的随机数		数组 哈希表 数学 3+	🔴	🀄️ 🔗