67. Add Binary

67. Add Binary (Easy)

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.

Related Topics:
Math, String

Similar Questions:

• Add Two Numbers (Medium)
• Multiply Strings (Medium)
• Plus One (Easy)
• Add to Array-Form of Integer (Easy)

Solution 1.

// 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;
    }
};