題目資訊

• 題目編號: 1980
• 題目連結: Find Unique Binary String
• 主題: Array, Hash Table, String, Backtracking

題目敘述

給定一個由字串組成的陣列 nums，其中包含 $n$ 個唯一的二進位字串，每個字串的長度為 $n$，返回一個長度為 $n$ 的二進位字串，該字串不會出現在 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” 也是正確的答案。

約束條件:

• $n == \text{nums.length}$
• $1 \leq n \leq 16$
• $\text{nums}[i].\text{length} == n$
• $\text{nums}[i]$ 是 '0' 或 '1'。
• nums 中所有的字串都是唯一的。

直覺

這個問題要求找到一個長度為 $n$ 的二進位字串，此字串不在給定的二進位字串列表中。列表中的每個字串都長度為 $n$，且所有字串都是唯一的。一個簡單的解決方法是利用這些字串的特性，系統性地構建一個新字串，使其與每一個輸入字串都故意有所不同。具體來說，考慮到問題的限制和結構，可以有效地利用對角線遍歷的方法。

解法

演算法的核心在於通過翻轉每個輸入字串中特定位置的字元來構建一個新的二進位字串。此方法確保新創建的字串在至少一個位置與所有輸入字串不同，使得這個新字串不可能出現在輸入列表中。

1. 初始化結果字串：從一個空字串開始，最終將持有不在 nums 中的二進位序列。

2. 遍歷輸入字串：對列表 nums 中的每個索引 i 的二進位字串進行遍歷。列表中有 $n$ 個字串，每個字串的自身長度為 $n$。

3. 構建不同的字串：

   • 在每個索引 i，關注字串 nums[i] 的第 $i$ 個字元。
   • 翻轉 nums[i] 的第 $i$ 個字元。具體而言，如果該字元是 ‘0’，則向結果字串中添加 ‘1’，如果是 ‘1’，則添加 ‘0’。
   • 這樣的操作可以確保所構建的字串至少在第 $i$ 個位置與輸入字串 nums[i] 不同。

4. 返回結果字串：一旦完成遍歷和操作，返回這個構建的字串。此字串保證不在 nums 中，因為它在每個位置第 $i$ 處與各個 nums[i] 字串不同。

5. 唯一性保證：由於 nums 中所有的輸入字串都是唯一的且 $n == \text{nums.length}$，此方法能可靠地生成一個不在 nums 裡的字串，滿足問題的要求。該方法利用翻轉對角線元素的特性來確保新創建字串不會對應於任何一個給定的字串。這種方法在給定的限制條件下既高效又具有簡單的邏輯性。

程式碼

C++

class Solution {
public:
    string findDifferentBinaryString(vector<string>& nums) {
        string result = "";

        // 遍歷陣列中的每個字串
        for (int i = 0; i < nums.size(); i++) {
            // 通過翻轉 nums 中第 i 個字串的第 i 個字符來構造新的二進位字串
            // （如果是 '0'，則在結果中加入 '1'; 如果是 '1'，則加入 '0'）
            result += nums[i][i] == '0' ? '1' : '0';
        }

        // 返回不存在於 nums 中的構造出的二進位字串
        return result;
    }
};

Python

class Solution:
    def findDifferentBinaryString(self, nums):
        result = ""

        # 遍歷數組中的每個字串
        for i in range(len(nums)):
            # 通過翻轉nums中第i個字串的第i個字符來構造一個新的二進位字串
            # （如果它是'0'，則在結果中附加'1'；如果它是'1'，則附加'0'）
            result += '1' if nums[i][i] == '0' else '0'

        # 返回構造的與nums中不重複的二進位字串
        return result

複雜度分析

• 時間複雜度: $O(n)$
  該算法精確地遍歷了 nums 陣列中的每一個字串一次，通過翻轉第 $i$ 個字串的第 $i$ 個字符來構造一個新的二進位字串。每次翻轉一個位元的操作是 $O(1)$，由於這個操作進行了 $n$ 次，因此整體時間複雜度是 $O(n)$。

• 空間複雜度: $O(n)$
  空間複雜度由正在構建的字串 result 決定。該字串的長度為 $n$ ，因為每次迭代都會向其中添加一個字符。因此，所需的額外空間與輸出字串的長度成正比，形成了 $O(n)$ 的空間複雜度。此複雜度不包括輸入的空間，因為在空間複雜度計算中通常不考慮輸入空間。