前往
大廳
主題

LeetCode - 1980. Find Unique Binary String 解題心得

Not In My Back Yard | 2022-01-31 00:00:05 | 巴幣 0 | 人氣 125

題目連結:


題目意譯:
給定一字串陣列 nums 其包含著 n 個相異的、每個長度為 n 的二元字串,回傳一個沒有出現於 nums 中的長度為 n 之二元字串。如果有多組可行解,則回傳任意一個。

限制:
n == nums.length
1 ≦ n ≦ 16
nums[i].length == n
nums[i] 只會是 '0' 或是 '1'。
所有 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" 也可被接受。


解題思維:
我們可以利用類似康托爾對角論證法(Cantor's Diagonal Argument,參見維基)的方式來構造出與每一個字串至少差一位的字串 S。

假設我們現在想要構造出 S[i] 應為何,那我們可以看 nums[i] 這個字串的第 i 位為 '0' 還是 '1'。

如果 nums[i][i] 是 '0',則我們把 S[i] 設為 '1';反之,我們把 S[i] 設為 '0'。

這樣一來,S 中的每一位數 S[i] 與相應的字串 nums[i] 最少會差在第 i 位有所不同。因此 S 將會與 nums 中所有字串至少差一位,因此 S 不會出現於 nums 中。

故 S 必為一種可行解,即所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作