LeetCode 1980 Find Unique Binary String 全解：回溯、Cantor 对角线、随机化与 Trie 五种思路及多语言实现

LeetCode 1980 Find Unique Binary String 全解回溯、Cantor 对角线、随机化与 Trie 五种思路及多语言实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文以 articles/find-unique-binary-string.md 为骨架系统讲解 LeetCode 1980「Find Unique Binary String」这道经典题的五种解法递归回溯、迭代回溯、Cantor 对角线构造、随机化与 Trie 前缀树。读者学完将掌握「在 2^n 个二进制串中高效找出缺失串」的证明思路与编码技巧并可在 Python、Java、C、Kotlin 等仓库多语言实现中直接对照验证。前置知识动手解题前建议先具备以下基础能力Hash Set利用集合的 O(1) 查找判断某个字符串是否已存在回溯 / 递归逐字符构造解空间并探索所有可能性二进制串处理整数与二进制字符串之间的互相转换、补零操作Cantor 对角线论证可选一种数学证明技术能保证构造出「与集合中每个元素都不同」的新元素是本体的最优解的理论根基。问题本质为什么缺失串一定存在给定一个长度为n的二进制字符串数组nums共n个串每个串长度也是n要求返回任意一个不在nums中出现过的长度为n的二进制串。关键洞察在于鸽巢原理长度为n的二进制串一共有2^n种而输入只有n个因此当n ≥ 1时必然2^n n缺失串一定存在。这一事实是所有解法尤其是随机化的正确性的前提。解法一回溯递归思路既然缺失串必然存在我们只需按字典序或任意顺序系统地构造候选串逐一检查是否出现在集合中。递归回溯从「全 0」串出发逐位尝试0与1第一个不在集合中的完整串即为答案。算法步骤将nums全部存入哈希集合获得 O(1) 查询从全0字符串开始递归在第i位若i n判断当前串是否在集合中不在则返回先保持第i位为0递归若失败将第i位改为1再递归返回第一个不在集合中的串。Python 实现class Solution: def findDifferentBinaryString(self, nums: List[str]) - str: strSet {s for s in nums} def backtrack(i, cur): if i len(nums): res .join(cur) return None if res in strSet else res res backtrack(i 1, cur) if res: return res cur[i] 1 return backtrack(i 1, cur) return backtrack(0, [0 for _ in nums])仓库源码对照仓库中 python/1980-find-unique-binary-string.py 与该实现完全一致且在每次失败分支后都显式检查并返回逻辑等价。其他语言版本同样遵循「先试 0 再试 1」的骨架java/1980-find-unique-binary-string.java 使用Set.of(nums)构建不可变集合并用StringBuffer递归kotlin/1980-find-unique-binary-string.kt 用CharArray与内联递归函数backtrack返回Boolean标志cpp/1980-find-unique-binary-string.cpp 则直接对0、1两个字符做 for 循环回溯push/pop并在成员变量result非空时提前剪枝返回。注意该 C 实现的时间复杂度注释为 O(2^N · N)遍历全部候选并拼接文档正文给出的递归版本因为「先试 0、失败才试 1」的贪心顺序实际只需访问少量节点均摊为 O(n²)。复杂度时间复杂度O(n²)空间复杂度O(n)递归栈 当前串解法二回溯迭代思路递归本质上是在隐式地遍历一棵二叉树。如果只想快速拿到一个答案可以直接遍历 0 到 n 的整数将其转换为定长二进制串后检查是否在集合中。因为只检查 n1 个候选而输入只有 n 个串必然能命中一个缺失串。算法步骤将nums存入哈希集合num从0遍历到n将num转成二进制串并用前导零补齐到长度n若不在集合中直接返回兜底返回空串理论上前 n1 个候选内必能找到。Python 实现class Solution: def findDifferentBinaryString(self, nums: List[str]) - str: strSet set(nums) n len(nums) for num in range(1 n): res bin(num)[2:].zfill(n) if res not in strSet: return res return 关键细节前导零补位各语言的补位手法各不相同这是本题最容易踩坑的地方Pythonbin(num)[2:].zfill(n)JavaString.format(% n s, Integer.toBinaryString(num)).replace( , 0)C自定义toBinaryString(int num, int length)逐位检查num (1 i)JavaScriptnum.toString(2).padStart(n, 0)Gofmt.Sprintf(%0*b, n, num)Rustformat!({:0width$b}, num, width n)。复杂度时间复杂度O(n²)空间复杂度O(n)解法三Cantor 对角线论证最优思路Cantor 对角线论证是本题最优雅、最快的解法时间复杂度 O(n)且完全不需要哈希集合。核心思想对每个输入串nums[i]取其第i个字符并翻转。构造出的串在第 0 位与nums[0]不同、在第 1 位与nums[1]不同……以此类推从而保证与每一个输入串至少在一位上不同。直觉上可以想象一个 n×n 的「字符串矩阵」我们沿着对角线取字符并全部取反得到的行必然与矩阵中的每一行都不同——这正是 Cantor 用来证明实数不可数的经典手法在本题的落地。算法步骤初始化空结果串对i从0到n-1读取对角线字符nums[i][i]追加其相反字符0变11变0返回结果串。Python 实现class Solution: def findDifferentBinaryString(self, nums: List[str]) - str: res [] for i in range(len(nums)): if nums[i][i] 0: res.append(1) else: res.append(0) return .join(res)验证示例以nums [01, 10]为例nums[0][0] 0→ 追加1nums[1][1] 0→ 追加1。结果11与01在第 0 位不同、与10在第 1 位不同确实不在输入中。复杂度时间复杂度O(n)空间复杂度O(1) 额外空间结果串本身 O(n)这是面试中最推荐的答案既无集合开销也无递归深度还附带一个漂亮的数学故事。解法四随机化思路利用「候选空间远大于输入规模」这一事实2^n个可能串中只有n个被占用随机生成一个串命中缺失串的概率至少为(2^n - n) / 2^n当n稍大时该概率趋近于 1。因此反复随机生成并查集合期望尝试次数非常小。算法步骤将nums存入哈希集合无限循环每位随机取0或1拼成长度为n的串若不在集合中则返回由于输入稀疏期望尝试次数极少。Python 实现class Solution: def findDifferentBinaryString(self, nums: List[str]) - str: strSet set(nums) n len(nums) while True: res .join(random.choice(01) for _ in range(n)) if res not in strSet: return res各语言随机源示例Java 用random.nextBoolean()、C 用rand() % 2、Go 用rand.Intn(2)、Rust 用rng.gen_bool(0.5)、Swift 用Bool.random()。复杂度时间复杂度最坏情况 O(∞)理论上有无限循环可能实际期望极快空间复杂度O(n)适用提示随机化解法代码最简但属于「概率性正确」面试讲解时应主动指出其期望复杂度与最坏情况体现严谨性。解法五Trie 前缀树思路用 Trie 存储所有输入串后从根节点出发寻找「断枝」若某节点缺少0或1子节点说明存在一条不经过任何已存串的路径沿该路径走下去并用任意字符补齐即可得到一个缺失串。算法步骤将所有输入串插入 Trie从根节点遍历若0子节点缺失追加0并返回剩余位置任意填充若1子节点缺失追加1并返回若两个子节点都存在优先走1继续深入若结果长度不足n用1补齐返回构造出的串。Python 实现class Node: def __init__(self): self.children [None, None] def contains_bit(self, bit: int) - bool: return self.children[bit] is not None def put(self, bit: int): self.children[bit] Node() def get(self, bit: int): return self.children[bit] class Trie: def __init__(self): self.root Node() def insert(self, s: str): curr self.root for c in s: bit int(c) if not curr.contains_bit(bit): curr.put(bit) curr curr.get(bit) def search(self, res: str, curr) - bool: while curr.contains_bit(0) or curr.contains_bit(1): if not curr.contains_bit(0): res.append(0) return True if not curr.contains_bit(1): res.append(1) return True res.append(1) curr curr.get(1) return False class Solution: def findDifferentBinaryString(self, nums: List[str]) - str: trie Trie() for s in nums: trie.insert(s) res [] trie.search(res, trie.root) while len(res) len(nums): res.append(1) return .join(res)原文档给出了 Node / Trie 拆分的完整多语言实现Java、C、JavaScript、C#、Go、Kotlin、Swift、Rust核心结构一致children[2]数组 containsBit / put / get三个方法Rust 版使用OptionBoxTrieNode表达可选子节点。复杂度时间复杂度O(n²)建树 O(n²)查找 O(n)空间复杂度O(n²)Trie 解法适合作为「数据结构选型」的展示当问题演化成需要多次查询或动态增删时前缀树结构能复用。常见陷阱陷阱一枚举全部 2^n 个候选虽然缺失串必然存在但直接遍历2^n个可能串是指数级开销n稍大就会超时。最优做法只需检查n1个候选解法二或直接使用 Cantor 对角线解法三。陷阱二忘记给二进制串补前导零整数转二进制后长度可能小于n例如n3时1应写成001而非1。忘记补零会导致生成的串长度错误无法与输入串正确比较。解法二的所有语言实现都显式做了补位请务必保留这一步。陷阱三误解 Cantor 对角线对角线法的精髓是翻转第 i 个串的第 i 个字符从而与每个串都在「自己那一行」不同。常见的错误是固定翻转某一位如总是翻转第一位这样只能保证与部分串不同无法覆盖全部输入。小结与仓库对照五种解法由「暴力」到「精巧」递进复杂度从 O(n²) 逐步收敛到 O(n)解法核心思路时间复杂度空间复杂度递归回溯逐位构造 集合去重O(n²)O(n)迭代回溯遍历 0..n 转定长二进制串O(n²)O(n)Cantor 对角线翻转对角线上每个字符O(n)O(1) 额外随机化概率命中缺失串期望极小O(n)Trie 前缀树沿缺失子节点构造O(n²)O(n²)本仓库围绕该题提供了可直接运行的完整实现Python、Java、C、Kotlin均以递归回溯为基线解法代码注释中标注了各自的复杂度分析适合作为刷题后的对照与复习材料。原文档 articles/find-unique-binary-string.md 还给出了其余语言JavaScript、C#、Go、Swift、Rust 等的完整 tab 实现可作为多语言横向对比的参考。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考