题目

给你一个字符串数组 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'

解题思路分析

1、哈希辅助；时间复杂度O(2^n)，空间复杂度O(n)

func findDifferentBinaryString(nums []string) string {
   n := len(nums)
   m := make(map[string]bool)
   for i := 0; i < len(nums); i++ {
      m[strings.Repeat("0", 16-n)+nums[i]] = true
   }
   for i := 0; i < (1 << n); i++ {
      if m[fmt.Sprintf("%016b", i)] == false {
         res := fmt.Sprintf("%016b", i)
         return res[16-n:]
      }
   }
   return ""
}

2、贪心；时间复杂度O(n)，空间复杂度O(1)

func findDifferentBinaryString(nums []string) string {
   n := len(nums)
   res := ""
   // 康托对角线
   // 只要和nums[i][i]不同，构造出的串就和所有的串都不同
   for i := 0; i < n; i++ {
      if nums[i][i] == '0' {
         res = res + "1"
      } else {
         res = res + "0"
      }
   }
   return res
}

总结

Medium题目，借助map来判断即可