Processing math: 100%

Leetcode 1980 - Find Unique Binary String

題目

Problem#

給你 n 個 binary string nums,其中每個 string 長度 n,要你回傳沒有出現在 nums 裏頭的 binary string。

測資限制#

  • 1n16

想法#

Naive: 把 num 建成 dict,n 很小,可以直接暴力枚舉 [1,2n]

AC Code#

Copy
class Solution {
public:
string findDifferentBinaryString(vector<string>& nums)
{
int n = nums.size();
int m = pow(2, n);
set<string> dict(nums.begin(), nums.end());
for(int i = 0; i < m; i++)
{
int tmp = i;
string s;
for(int i = 0; i < n; i++)
{
s += to_string(tmp & 1);
tmp >>= 1;
}
reverse(s.begin(), s.end());
if(!dict.count(s))
return s;
}
return "";
}
};
view raw leetcode/1980.cpp delivered with ❤ by emgithub
  • 時間複雜度: O(2n)
  • 空間複雜度: O(2n)