Leetcode 1980. 找出不在清單中的二進位字串

這是 Leetcode 2025 年 2 月 20 日的每日一題。

題目描述

#

給定一個長度為 n 的字串陣列 nums，其中包含 n 個不重複的二進位字串，每個字串長度也為 n。請回傳一個長度為 n 且不在 nums 中出現過的二進位字串。

解題直覺

#

• 這題可以利用康托爾對角線法（Cantor’s diagonal argument）來解，我們只需要實作它即可。

解題思路

#

1. nums 是一個包含 n 個不同的二進位字串，每個字串長度為 n。

2. 為了生成一個保證不重複的新字串，我們可以：

   • 取出每個字串的第 i 個字元，即對角線元素 nums[i][i]。

   • 如果 nums[i][i] 是 0，我們將它改為 1； 如果是 1，則改為 0。

3. 因為新字串在第 i 位和 nums[i] 不同，所以它必然不會等於任何一個原本的字串。

Code

#

string findDifferentBinaryString(vector<string>& nums) {
        string result = "";
        for(int i = 0; i < nums.size(); i++){
            result += (nums[i][i] == '0') ? '1' : '0';
        }
        return result;
    }

時間複雜度：$O(n)$

空間複雜度：$O(1)$（不計輸出字串）

感謝閱讀！歡迎分享你的想法與回饋！