📘 題目敘述
給你一個字串陣列 nums，其中包含 n 個互不相同的二進位字串，且每個字串長度都是 n。請你回傳一個長度為 n 的二進位字串，且不出現在 nums 裡。
如果有多個答案，你可以回傳其中任意一個。
條件限制
n == nums.length1 <= n <= 16nums[i].length == nnums[i]只包含'0'或'1'nums中所有字串皆互不相同
🧠 解題思路
我的做法是：先用遞迴把所有長度為 n 的二進位字串都生成出來（總共 2^n 個），把它存成 all。
因為題目保證 nums 裡有 n 個、且都不同，而 2^n 至少是 n（n<=16 時更是遠大於等於），所以 all 一定會有某個字串不在 nums 裡。
接著我把 nums 排序後，從左到右比對：
- 如果在某個位置
i，出現nums[i] != all[i]，那all[i]就是第一個不一樣的字串，它一定不在nums裡（因為排序後若all[i]在nums中，理論上會對齊在同一個位置）。 - 如果全部都一樣，代表
nums其實剛好是all的前面n個，那我就回傳all的最後一個字串all[all.size() - 1]，它一定不會在nums裡。
所有變數
n：每個二進位字串的長度（也是nums的長度）v：在allbinary(n)遞迴中，存allbinary(n-1)的結果ans：在allbinary(n)中，用來存最後生成的所有長度n的字串all：allbinary(n)生成的所有長度為n的二進位字串（大小2^n）
🪜 主要流程步驟
1. 遞迴函數 allbinary(n)：生成所有長度為 n 的二進位字串
這個函數的目標是回傳一個 vector<string>，裡面放著所有長度為 n 的二進位字串。
(1) Base case：n == 1
直接回傳 {"0", "1"}，因為長度 1 的二進位字串只有這兩個。
(2) 遞迴生成：由 allbinary(n-1) 擴展到 allbinary(n)
- 先遞迴拿到
v = allbinary(n - 1)，此時v裡每個字串長度都是n-1。 - 接著做兩輪擴展：
- 第一輪：對每個
s in v，在前面加'0'，變成長度n，推進ans。 - 第二輪：對每個
s in v，在前面加'1'，變成長度n，推進ans。
- 第一輪：對每個
這樣 ans 就包含了所有長度 n 的二進位字串，而且數量是 2 * 2^(n-1) = 2^n。
2. 主函數 findDifferentBinaryString(nums)：找出不在 nums 的那個字串
(1) 取得 n，並生成 all
n = nums[0].size()all = allbinary(n)：生成所有長度n的二進位字串
(2) 將 nums 排序
sort(nums.begin(), nums.end())
(3) 逐一比對 nums 與 all
- 從
i = 0到nums.size()-1： - 如果
nums[i] != all[i]，直接回傳all[i]
(4) 若都相同，回傳 all 的最後一個
return all[all.size() - 1]
因為 nums 只有 n 個，而 all 有 2^n 個，所以最後那個一定不在 nums 裡。
⏱️ 複雜度
- 時間複雜度：
O(2^n * n + n log n)- 生成全部字串：
2^n個、每個長度n - 排序
nums：O(n log n)（這裡的n是字串數量）
- 生成全部字串：
- 空間複雜度：
O(2^n * n)all存下所有字串
💻 程式碼實作
class Solution {
public:
vector<string> allbinary(int n) {
if (n == 1) {
return {"0", "1"};
}
vector<string> v;
vector<string> ans;
v = allbinary(n - 1);
for (string s : v) {
ans.push_back('0' + s);
}
for (string s : v) {
ans.push_back('1' + s);
}
return ans;
}
string findDifferentBinaryString(vector<string>& nums) {
int n = nums[0].size();
auto all = allbinary(n);
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != all[i]) {
return all[i];
}
}
return all[all.size() - 1];
}
};
🔗 題目連結
https://leetcode.com/problems/find-unique-binary-string/