67. Add Binary

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"

string addBinary(string a, string b) { // time: O(m + n); space: O(m + n)
    int m = a.length(), n = b.length(), carry = 0;
    string res;
    for (int i = m - 1, j = n - 1; i >= 0 || j >= 0 || carry; --i, --j) {
        int tmp = (i >= 0 ? (a[i] - '0') : 0) + (j >= 0 ? (b[j] - '0') : 0) + carry;
        carry = tmp / 2;
        tmp %= 2;
        res += (tmp + '0');
    }
    reverse(res.begin(), res.end());
    return res;
}