Add Binary

Add Binary

Given two binary strings, return their sum (also a binary string).
For example,
a = "11"
b = "1"
Return "100".

Naive Way: 直观的感受就是直接加，像列竖式一样，用一个变量记录进位。唯一的区别可能就是是否使用extra space. 如果说用原来的某一个String作载体承接输出String, 看似没有使用extra space，但由于在Java中String 是immutable的（什么是immutable)，对String的某一位置的改动都必须重新创建一个新的String来承接，所以就算用原有的String也无法做到no extra space。我做的时候考虑了一下StringBuilder.insert()好像也要O(n)，就先用一个Stack存下字符，最后一并推出，但实际上和用StringBuilder.insert()的实际时间比没有任何什么差别。

之所以不用String 而用StringBuilder是因为String每次改动都要创建一个新的String对象，这样就需要很多的extra space。


// 这是我第二次写的
public class Solution {
    public String addBinary(String a, String b) {
        Stack<Character> stack = new Stack<Character>();
        StringBuilder s = new StringBuilder();
        if(a.length() < b.length())
            return addBinary(b,a);
        int carry = 0;
        int j = a.length()-1,i = b.length()-1;
        while(j >= 0 && i >= 0){
            carry += a.charAt(j--)=='1'?1:0;
            carry += b.charAt(i--)=='1'?1:0;
            stack.push((char)(carry%2 + '0'));
            carry /= 2;
        }
        while(j >= 0){
            carry += a.charAt(j--)=='1'?1:0;
            stack.push((char)(carry%2 + '0'));
            carry /= 2;
        }
        if(carry==1)
            stack.push('1');
        while(!stack.isEmpty()){
            s.append(stack.pop());
        }
        return s.toString();
    }
}


// 这是我第一次写的，用了一个reverse()的方法
public String addBinary(String a, String b) {
            boolean forward =false;
            String rslt = "";
            int i = a.length()-1;
            int j = b.length()-1;
            while(i >= 0 && j >= 0){
                if(a.charAt(i) == '1' && b.charAt(j) == '1' && forward){
                    rslt += '1';
                    forward = true;
                }else if(((a.charAt(i) == '1' || b.charAt(j) == '1') && forward) || (a.charAt(i) == '1' && b.charAt(j) == '1')){
                    rslt += '0';
                    forward = true;
                }else if(a.charAt(i) == '1' || b.charAt(j) == '1' || forward){
                    rslt += '1';
                    forward = false;
                }else{
                    rslt += '0';
                    forward = false;
                }
                i--;
                j--;
            }
            while(i >= 0){
                if(a.charAt(i) == '1' && forward){
                    rslt += '0';
                    forward = true;
                }else{
                    rslt += (a.charAt(i) == '1'||forward)?'1':'0';
                    forward = false;
                }
                i--;
            }
            while(j >= 0){
                if(b.charAt(j) == '1' && forward){
                    rslt += '0';
                    forward = true;
                }else{
                    rslt += (b.charAt(j) == '1'||forward)?'1':'0';
                    forward = false;
                }
                j--;
            }
            if(forward){rslt += '1';}
           
            // reverse the rslt
            String reverse = new StringBuffer(rslt).reverse().toString();
            return reverse;
        }