題目連結:
題目意譯:
給定一字串陣列 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 必為一種可行解,即所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。