Medium

题目描述

给定一个字符串数组 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对角化（推荐） 这是最巧妙的解法，基于Cantor对角化定理。我们构造一个新的二进制字符串，使得它在第 i 位上的值与 nums[i] 的第 i 位不同。这样构造出的字符串必然不会与数组中的任何字符串相同。

方法二：哈希表 + 枚举 将所有给定的二进制字符串存入哈希表，然后枚举所有可能的长度为 n 的二进制字符串（从 0 到 2^n-1），找到第一个不在哈希表中的字符串。

方法三：递归回溯 使用递归逐位构造二进制字符串，每次尝试添加 ‘0’ 或 ‘1’，如果当前构造的字符串可能与某个给定字符串匹配，则进行剪枝。

其中方法一最为巧妙且效率最高，时间复杂度仅为 O(n)，是最推荐的解法。

代码实现

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        string result = "";
        for (int i = 0; i < nums.size(); i++) {
            // 对角化：第i位与nums[i]的第i位不同
            result += (nums[i][i] == '0') ? '1' : '0';
        }
        return result;
    }
};

class Solution:
    def findDifferentBinaryString(self, nums: List[str]) -> str:
        result = ""
        for i in range(len(nums)):
            # 对角化：第i位与nums[i]的第i位不同
            result += '1' if nums[i][i] == '0' else '0'
        return result

public class Solution {
    public string FindDifferentBinaryString(string[] nums) {
        StringBuilder result = new StringBuilder();
        for (int i = 0; i < nums.Length; i++) {
            // 对角化：第i位与nums[i]的第i位不同
            result.Append(nums[i][i] == '0' ? '1' : '0');
        }
        return result.ToString();
    }
}

var findDifferentBinaryString = function(nums) {
    let result = "";
    for (let i = 0; i < nums.length; i++) {
        // 对角化：第i位与nums[i]的第i位不同
        result += nums[i][i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型Cantor对角化哈希表枚举递归回溯
时间复杂度O(n)O(n + 2^n)O(2^n)
空间复杂度O(1)O(n)O(n)

推荐使用 Cantor对角化方法，它具有最优的时间和空间复杂度。

相关题目