LeetCode 解題紀錄 1980. Find Unique Binary String

Find Unique Binary String - LeetCode

題目

給定一個 n 個不同 binary 格式字串陣列 nums ，返回任何一個沒有出現在陣列中，長度也是 n 的 binary 字串

限制

• nums.length = n
• nums[i].length = n
• 1 ≤ n ≤ 16

觀察

• binary 字串長度最長為 16，可以放心轉成 Integer

思路

• 陣列長度不超過 16，可以用暴力法找 n+1 個數字一定有一個不包含在 nums
• 先將陣列中的字串轉成數字集合，然後從 0 開始加，回傳第一個不在集合中的數字

Trial 1

結果

時間複雜度為 O(n²)，空間複雜度為 O(n)

Trial 2

• 使用 DFS 來找尋所有字串，回傳找到第一個不在集合中的字串

結果

時間與空間複雜度為 O(2^n)

Trial 3

• 這是討論串中提出的最佳解，理論可以在這裡找到，基本上長度為 n 的位元組只有 n 個時，只要任意找一個位元與其相反，組成的位元串必定不會跟該字串相同，這樣就能保證一次就找到不同的

結果

時間與空間複雜度為 O(n)