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"
``````

``````class Solution {

public String addBinary(String a, String b) {
StringBuilder sb = new StringBuilder();
int i = a.length() - 1, j = b.length() - 1, carry = 0;
while(i >= 0 || j >= 0){
int sum = carry;
if(i>=0) sum += a.charAt(i--) - '0';
if(j>=0) sum += b.charAt(j--) - '0';
sb.append(sum % 2);
carry = sum / 2;
}
if(carry > 0 ) sb.append(carry);
return sb.reverse().toString();
}
}
``````

Python:

``````class Solution(object):
"""
:type a: str
:type b: str
:rtype: str
"""
res = []

i, j = len(a) - 1, len(b) - 1;
carry = 0

while i >= 0 or j >= 0:
total = carry
if i >= 0:
total += int(a[i])
i -= 1
if j >= 0:
total += int(b[j])
j -= 1
res.append(`total % 2`)
carry = total / 2

if carry:
res.append(`carry`)

return "".join(res)[::-1]
``````