LeetCode 1980 题通关指南｜3种解法拆解“找唯一未出现二进制串”问题，附Python最优解实现

目录

一、题目重述与核心分析

1.1 题目要求

给定一个字符串数组 nums，满足：

• 数组长度为 n，且包含 n 个互不相同的二进制字符串；

• 每个字符串的长度也为 n。

要求找出并返回一个长度为 n、未出现在 ** nums ** 中 的二进制字符串（任意一个符合条件的即可）。

1.2 核心概念解释

• 二进制字符串：仅由 ‘0’ 和 ‘1’ 组成的字符串，长度为 n 的二进制字符串总共有 2ⁿ 种可能；

• 核心矛盾：题目中仅给出 n 个不同的二进制串，而 2ⁿ ≥ n+1（当 n≥1 时恒成立），因此必然存在至少一个符合条件的字符串；

• 示例拆解：

  • 示例1：nums = ["01","10"]（n=2），总共有4种二进制串（00、01、10、11），返回11或00均可；

  • 示例2：nums = ["00","01"]（n=2），未出现的是10/11，返回任意一个即可；

  • 示例3：nums = ["111","011","001"]（n=3），未出现的有000、010、100、101等，返回101即可。

1.3 题目本质

本题的核心是从 ** 2ⁿ ** 种可能的二进制串中，找到一个不在给定集合中的元素。由于 n≤16，2¹⁶=65536，即使暴力枚举也能轻松通过，而最优解（康托对角线法）可在 O(n) 时间内直接构造结果。

二、解题思路拆解

核心逻辑

长度为 n 的二进制字符串总共有 2ⁿ 种，而输入仅包含 n 个，因此：

思路优势对比

三、多解法代码实现（Python）

严格遵循题目要求的代码格式（函数名修正为 findDifferentBinaryString，参数为 nums: List[str]）。

解法一：暴力枚举（直观易懂）

解题逻辑

代码实现

from typing import List

class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
n = len(nums)

# 生成所有长度为n的二进制字符串（从0到2^n-1，转二进制补零）
for num in range(2 ** n):
# 将数字转为二进制字符串，去掉前缀'0b'，补零到n位
binary = bin(num)[2:].zfill(n)
# 检查是否不在nums中
if binary not in nums:
return binary

# 题目保证必有解，此处仅为兜底
return ""

解法二：哈希集合+枚举（优化效率）

解题逻辑

代码实现

from typing import List

class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
n = len(nums)
# 将nums存入集合，O(1)查询
num_set = set(nums)

# 枚举所有可能的二进制字符串
for num in range(2 ** n):
binary = bin(num)[2:].zfill(n)
if binary not in num_set:
return binary

return ""

解法三：康托对角线法（最优解）

解题逻辑

代码实现

from typing import List

class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
n = len(nums)
res = []
# 遍历每个字符串的第i位，取反后拼接
for i in range(n):
# 取第i个字符串的第i位，取反
bit = '1' if nums[i][i] == '0' else '0'
res.append(bit)
# 拼接为最终字符串
return ''.join(res)

四、代码解析与边界测试

4.1 代码关键细节

解法一（暴力枚举）

• bin(num)[2:]：将数字转为二进制字符串，去掉前缀 0b（如 bin(3) → '11'）；

• zfill(n)：补零到指定长度（如 '1' 补零到2位 → '01'）；

• 时间复杂度 O(n·2ⁿ)：枚举 2ⁿ 个字符串，每个字符串查询 nums 需 O(n) 时间；

• 适用场景：n 较小时（如 n≤10），逻辑简单易理解。

解法二（哈希集合+枚举）

• 哈希集合 num_set 存储 nums，查询时间从 O(n) 降至 O(1)；

• 时间复杂度优化为 O(2ⁿ)，空间复杂度 O(n²)（存储 n 个长度为 n 的字符串）；

• 适用场景：n 中等（如 n≤16），效率优于暴力枚举。

解法三（康托对角线法）

• 核心逻辑：构造的字符串与 nums[i] 的第 i 位不同，因此必然不在 nums 中；

• 示例验证（示例1：nums = ["01","10"]）：

  • i=0：nums[0][0] = '0' → 取反为 '1'；

  • i=1：nums[1][1] = '0' → 取反为 '1'；

  • 构造结果为 '11'，与示例1输出一致；

• 时间/空间复杂度均为 O(n)，最优解，适配所有 n 范围。

4.2 边界场景测试

4.3 示例测试验证

• 示例1：输入 nums = ["01","10"]

  • 解法三构造：nums[0][0]='0'→'1'，nums[1][1]='0'→'1' → 返回 "11"（符合示例输出）；

• 示例2：输入 nums = ["00","01"]

  • 解法三构造：nums[0][0]='0'→'1'，nums[1][1]='1'→'0' → 返回 "10"（示例中正确答案之一）；

• 示例3：输入 nums = ["111","011","001"]

  • 解法三构造：nums[0][0]='1'→'0'，nums[1][1]='1'→'0'，nums[2][2]='1'→'0' → 返回 "000"（示例中正确答案之一）。

五、复杂度对比与优化思路

5.1 复杂度详细分析

5.2 优化思路解析

核心是用空间换时间，哈希集合存储所有输入字符串，将每次查询的时间从 O(n) 降至 O(1)，当 n=16 时，2¹⁶=65536，哈希优化可减少大量重复查询；

康托对角线法是本题的“点睛之笔”——利用“对角线取反”直接构造结果，无需枚举所有可能，时间复杂度从指数级降至线性级，是算法竞赛中的经典技巧。

六、常见误区与避坑指南

错误逻辑：bin(num)[2:] 直接返回，未补零到 n 位（如 num=1，n=2 时返回 '1' 而非 '01'）；

避坑：必须使用 zfill(n) 补零，确保生成的字符串长度为 n。

错误逻辑：认为“取反任意位”即可，而非“第 i 个字符串的第 i 位”；

避坑：对角线取反的核心是“每个输入串都有至少一位不同”，若随机取反，可能构造出已存在的字符串。

错误认知：2¹⁶=65536 枚举会超时；

避坑：Python 处理 65536 次循环仅需毫秒级，完全满足题目要求，且康托对角线法可彻底避免枚举。

错误逻辑：假设输入字符串长度均为 n，但代码未做校验；

避坑：题目明确说明 nums[i].length == n，无需额外校验，但实际开发中可添加断言增强健壮性。

七、总结与扩展思考

7.1 解题核心

本题的核心是利用二进制字符串的特性，找到未出现的元素，三种解法体现了“从暴力到最优”的优化思路：

7.2 扩展思考

提示：康托对角线法不再适用，需改为枚举长度为 m 的二进制字符串，哈希优化仍有效。

提示：暴力枚举/哈希枚举按字典序生成，返回第一个未出现的即可。

提示：康托对角线法仍是唯一选择，枚举法会因 2¹⁰⁰⁰ 无法处理而失效。

7.3 算法启示

• 哈希表是“查询类”问题的常用优化手段，可将线性查询转为常数级；

• 构造法是算法竞赛中的高级技巧，能避免枚举，直接得到结果；

• 解题时应先保证正确性，再逐步优化效率，符合“先暴力后优化”的思维逻辑。

总结