Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contains only characters 1 or 0.
Example 1:
Input: a = "11", b = "1" Output: "100"
Example 2:
Input: a = "1010", b = "1011" Output: "10101"
Constraints:
- Each string consists only of
'0'or'1'characters. 1 <= a.length, b.length <= 10^4- Each string is either
"0"or doesn't contain any leading zero.
Similar Questions:
- Add Two Numbers (Medium)
- Multiply Strings (Medium)
- Plus One (Easy)
- Add to Array-Form of Integer (Easy)
// OJ: https://leetcode.com/problems/add-binary/
// Author: github.com/lzl124631x
// Time: O(A+B)
// Space: O(1)
class Solution {
public:
string addBinary(string a, string b) {
int i = a.size() - 1, j = b.size() - 1, carry = 0;
string ans;
while (i >= 0 || j >= 0 || carry) {
if (i >= 0) carry += a[i--] - '0';
if (j >= 0) carry += b[j--] - '0';
ans += '0' + (carry & 1);
carry >>= 1;
}
reverse(begin(ans), end(ans));
return ans;
}
};