數論技巧題 造出等長的新二進位字串Find Unique Binary String Leetcode #1980

這題的題目在這裡: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.length
• 1 <= n <= 16
• nums[i].length == n
• nums[i] is either '0' or '1'.
• All the strings of nums are 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