题目

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

解题思路

这道题最经典、最优雅的解法是利用康托尔对角线法（Cantor's Diagonal Argument）。

因为数组 nums 中恰好有 $n$ 个字符串，且每个字符串的长度也正好是 $n$。我们可以巧妙地构造一个新的二进制字符串：让新字符串的第 $i$ 个字符与 nums[i] 的第 $i$ 个字符完全相反（即 '0' 变 '1'，'1' 变 '0'）。

这样一来，我们构造出的新字符串在第 $i$ 个位置上一定与 nums[i] 不同。这就保证了新字符串绝对不可能等于 nums 中的任何一个字符串。

具体代码

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        # 遍历对角线上的字符并将其反转
        return "".join('1' if nums[i][i] == '0' else '0' for i in range(len(nums)))