這題的題目在這裡:Find Unique Binary String
題目敘述
題目會給我們一個字串陣列nums，內容都是二進位字串，要求我們造出一個另一個相等長度，新的二進位字串，而且不和字串陣列nums內的重複。答案可能有不只一組，回傳合任一組合法的答案皆可。
測試範例
Example 1:
Input: nums = ["01","10"]
Output: "11"
Explanation: "11" does not appear in nums. "00" would also be correct.
Example 2:
Input: nums = ["00","01"]
Output: "11"
Explanation: "11" does not appear in nums. "10" would also be correct.
Example 3:
Input: nums = ["111","011","001"]
Output: "101"
Explanation: "101" does not appear in nums. "000", "010", "100", and "110" would also be correct.
約束條件
Constraints:
n == nums.length1 <= n <= 16nums[i].length == nnums[i]is either'0'or'1'.- All the strings of
numsare unique.
演算法
其實這邊可以利用到在數論中，證明實數集合是不可數集，包含有無窮多的小數，可以無窮分割的康託對角線證明技巧。
把每個已知的二進位字串視為軸線，那麼要造出新的等長不重複二進位字串，依照康託對角線的原則，就變得很簡單。
舉例來說:
nums 給定 "111","011","001" 視為已知
那麼
1 1 1
0 1 1
0 0 1
排列好之後，把對角線的bit作翻轉(特別標黑粗體的部分)，0翻轉成1，1翻轉成0，就可以造出另一個相等長度，新的二進位字串 "000"
再舉一個例子
nums 給定 "01","10" 視為已知
那麼
0 1
1 0
排列好之後，把對角線的bit作翻轉(特別標黑粗體的部分)，0翻轉成1，1翻轉成0，就可以造出另一個相等長度，新的二進位字串 "11"
程式碼
class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
binary = []
# Use the trick like Cantor's diagonal argument
for i in range(len(nums)):
if nums[i][i] == "0":
binary.append("1")
else:
binary.append("0")
return "".join(binary)
複雜度分析
時間複雜度: O(n)
一次線性掃描，掃描長度和字串長度一樣長。
空間複雜度: O(n)
過程中，會使用到暫存的buffer array: binary
關鍵知識點
除了傳統的暴力法展開，去一個一個比對，去除重複的二進位字串。
也可以使用康託對角線證明技巧。
把每個已知的二進位字串視為軸線，把原本的01互相翻轉，造出新的等長不重複二進位字串。
Reference:
[1] Python O(n) by Cantor's diagonal [w/ Visualization] - Find Unique Binary String - LeetCode
