67. Add Binary
1. Description
Given two binary strings a and b, return their sum as a binary string.
2. Example
Example 1:
Input: a = “11”, b = “1”
Output: “100”
Example 2:
Input: a = “1010”, b = “1011”
Output: “10101”
3. Constraints
- 1 <= a.length, b.length <= $10^4$
- a and b consist only of ‘0’ or ‘1’ characters.
- Each string does not contain leading zeros except for the zero itself.
4. Solutions
My Accepted Solution
n = max(m_str1.size(), m_str2.size())
Time complexity: O(n)
Space complexity: O(1)
class Solution {
public:
string addBinary(const string &a, const string &b) {
const string &long_str = a.size() >= b.size() ? a : b;
const string &short_str = a.size() >= b.size() ? b : a;
string sum(long_str.size(), 0);
int i = long_str.size() - 1, j = short_str.size() - 1;
int carry = 0;
for (; i >= 0; --i, --j) {
sum[i] = (long_str[i] - '0' + (j >= 0 ? short_str[j] : '0') - '0' + carry) % 2 + '0';
carry = (long_str[i] - '0' + (j >= 0 ? short_str[j] : '0') - '0' + carry) / 2;
}
if (carry == 1) {
sum.insert(sum.begin(), '1');
}
return sum;
}
};