Given an array of strings nums containing n unique binary strings each of length n, return a binary string of length n that does not appear in nums. If there are multiple answers, you may return any of them.
Example 1:
Input: nums = ["01","10"] Output: "11" Explanation: "11" does not appear in nums. "00" would also be correct.
Example 2:
Input: nums = ["00","01"] Output: "11" Explanation: "11" does not appear in nums. "10" would also be correct.
Example 3:
Input: nums = ["111","011","001"] Output: "101" Explanation: "101" does not appear in nums. "000", "010", "100", and "110" would also be correct.
Constraints:
n == nums.length1 <= n <= 16nums[i].length == nnums[i]is either'0'or'1'.- All the strings of
numsare unique.
Solution 1: Hashtable
We can use bitset to convert between integer and binary string.
Time complexity: O(n2)
Space complexity: O(n2)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua class Solution { public: string findDifferentBinaryString(vector<string>& nums) { const int n = nums.size(); unordered_set<int> seen(1 << n); for (const string& num : nums) seen.insert(bitset<16>(num).to_ulong()); for (int i = 0; i < 1 << n; ++i) if (!seen.count(i)) return bitset<16>(i).to_string().substr(16 - n); return ""; } }; |
Solution 2: One bit a time
Let ans[i] = ‘1’ – nums[i][i], s.t. ans is at least one bit different from any strings.
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua class Solution { public: string findDifferentBinaryString(vector<string>& nums) { const int n = nums.size(); string ans(n, '0'); for (int i = 0; i < n; ++i) ans[i] = '1' - nums[i][i] + '0'; return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment