Given two binary strings, return their sum (also a binary string).

For example,

a = "11"
b = "1"
Return "100".

从后向前加即可，最后判断一下carry = 1的case。
Time Complexity - O(n)， Space Complextiy O(1)

public class Solution {
    public String addBinary(String a, String b) {
        if(a == null || b == null) return "";
        int i=a.length()-1, j = b.length()-1;
        int[] digits = new int[i+j+2];
        int k = digits.length -1;
        int carry = 0;
        while(i >=0 || j>=0){
            int digitA = (i>=0)? (a.charAt(i) - '0') : 0;
            int digitB = (j>=0)? (b.charAt(j) - '0') : 0;
            digits[k--] = (digitA + digitB + carry)%2;
            carry = (digitA + digitB + carry >=2)? 1:0;
            i--;
            j--;
        }
        
        if(carry == 1) digits[k] = 1;
        StringBuilder sb = new StringBuilder();
        for(int digit : digits){
            if(digit == 0 && sb.length() == 0) continue;
            sb.append(digit);
        }
        if(sb.length() == 0) return "0";
        return sb.toString();
    }
}