Leetcode Problem:
Summary
- Given an array of unique binary strings, return a binary string that does not appear in the array.
Approach
- The solution uses a set data structure to store the binary numbers represented by the input strings
- It then iterates over all possible binary numbers of the same length as the input strings, checks if each number is in the set, and returns the first number that is not in the set.
Complexity
- O(2^n * n) where n is the length of the input strings
Explanation
- The solution first converts each binary string to a decimal number using the `makeNum` function
- It then stores these decimal numbers in a set
- The `makeStr` function is used to convert a decimal number back to a binary string
- The solution then iterates over all possible binary numbers of the same length as the input strings, checks if each number is in the set, and returns the first number that is not in the set
- This approach ensures that the solution finds the first binary string that does not appear in the input array.
Solution Code:
class Solution {
public:
int makeNum(string s){
int num = 0;
for(int i = 0 ; i < s.size(); i++){
num *= 2;
num += s[i] - '0';
}
return num;
}
string makeStr(int num, int length){
string res = "";
for(int i = 0 ; i < length; i++){
res = string(1, '0'+(num %2)) + res;
num /= 2;
}
return res;
}
bool set[1<<16];
string findDifferentBinaryString(vector& nums) {
int length = nums[0].size();
for(int i = 0 ; i < nums.size(); i++){
set[makeNum(nums[i])] = true;
}
for(int i = 0 ; i < (1 << 16); i++){
if(set[i]){
continue;
}
return makeStr(i, length);
}
return "";
}
};
class Solution {
public:
int makeNum(string s){
int num = 0;
for(int i = 0 ; i < s.size(); i++){
num *= 2;
num += s[i] - '0';
}
return num;
}
string makeStr(int num, int length){
string res = "";
for(int i = 0 ; i < length; i++){
res = string(1, '0'+(num %2)) + res;
num /= 2;
}
return res;
}
bool set[1<<16];
string findDifferentBinaryString(vector& nums) {
int length = nums[0].size();
for(int i = 0 ; i < nums.size(); i++){
set[makeNum(nums[i])] = true;
}
for(int i = 0 ; i < (1 << 16); i++){
if(set[i]){
continue;
}
return makeStr(i, length);
}
return "";
}
};
'알고리즘' 카테고리의 다른 글
| Largest Combination With Bitwise AND Greater Than Zero (0) | 2025.02.21 |
|---|---|
| Find if Array Can Be Sorted (0) | 2025.02.21 |
| Minimum Number of Changes to Make Binary String Beautiful (0) | 2025.02.20 |
| String Compression III (0) | 2025.02.20 |
| Rotate String (0) | 2025.02.20 |
짬뽕얼큰하게
