What is the simplest approach to find a unique binary string in this problem?

Use a hash set to store all input strings, then generate candidates by integer conversion or backtracking until a missing string is found.

Can multiple correct outputs exist for Find Unique Binary String?

Yes, any binary string of length n not in nums is valid, so multiple answers are acceptable.

How does the diagonal method guarantee a unique string?

By flipping the i-th bit of the i-th string, the resulting string differs from each input string in at least one position.

Is converting binary strings to integers necessary?

Not strictly, but it allows O(1) lookup in a hash set and simplifies candidate generation for larger n.

What is the time complexity pattern for this problem?

The array scanning plus hash lookup pattern ensures O(n) time, avoiding full enumeration of all 2^n strings.

#1980

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

找出不同的二进制字符串

给你一个字符串数组 nums ，该数组由 n 个互不相同的二进制字符串组成，且每个字符串长度都是 n 。请你找出并返回一个长度为 n 且没有出现在 nums 中的二进制字符串。如果存在多种答案，只需返回任意一个即可。示例 1：输入： nums = ["01","10"] 输出： …

数组哈希表字符串回溯

题目描述

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

lightbulb

解题思路

方法一：计数 + 枚举

由于 '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)$ 。

1

2

3

4

5

6

7

8

9

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)

speed

复杂度分析

指标	值
时间	complexity is O(n) because each string check or construction involves iterating through n strings of length n. Space complexity is O(1) if using in-place construction or minimal auxiliary storage for hash sets.
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Will you convert strings to integers for faster lookup?
question_mark
Can you explain how backtracking can generate a valid missing string?
question_mark
Is there a direct O(n) way without checking all 2^n candidates?

warning

常见陷阱

外企场景

error
Assuming only one correct output exists instead of recognizing multiple valid strings.
error
Failing to maintain fixed string length when converting integers back to binary.
error
Attempting naive iteration over all 2^n strings, which can exceed time limits for n=16.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Return all missing binary strings instead of any single one.
arrow_right_alt
Find a unique binary string with additional constraints on number of 1s.
arrow_right_alt
Handle larger n efficiently by using bit manipulation tricks.

help

常见问题

外企场景

继续练习

#1948 删除系统中的重复文件夹 #2023 连接后等于目标字符串的字符串对 #2053 数组中第 K 个独一无二的字符串