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();
}
}
