67. Add Binary (Easy) Facebook

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

For example,
a ="11"
b ="1"
Return"100".

Solution 1: StringBuilder append() O(n); O(n)

    /**
     * Math. String.
     * LeetCode第2题的简化版
     * When we do addition, we start from the lowest order.
     * So for this question, we need to scan the string from end to start, do it digit-by-digit.
     * Get current digits of ab and b, add them up.
     * Also use an integer to store carry from the previous addition.
     * Store the sum to result and update carry for each round.
     * Stop when longest string is reached.
     * Remember to check carry before return, if carry is 1, it should still be inserted to the result.
     */    
    public String addBinary(String a, String b) {
        if (a == null || b == null) {
            return "";
        }

        int i = a.length() - 1;
        int j = b.length() - 1;
        int carry = 0;
        StringBuilder res = new StringBuilder();
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (i >= 0) {
                sum += a.charAt(i--) - '0';
            }
            if (j >= 0) {
                sum += b.charAt(j--) - '0';
            }
            res.append(sum % 2); //得到sum的低位
            carry = sum / 2; //得到sum的高位
        }
        if (carry != 0) {
            res.append(carry);
        }
        return res.reverse().toString();
    }

Solution 2: StringBuilder insert() O(n^2); O(n)

    /**
     * Math. String.
     * Initialize two pointers i and j at the end of a and b.
     * Use one integer c for the carry.
     * While i >= 0 or j >= 0 or c == 1:
     * | Add char in a or 0 to carry c. Move i.
     * | Add char in b or 0 to carry c. Move j.
     * | c % 2 is the current digit.
     * | Insert current digit to the front of result.
     * | c / 2 is the next carry.
     * Return result string.
     */    
    public String addBinary(String a, String b) {
        StringBuilder sum = new StringBuilder();
        int i = a.length() - 1;
        int j = b.length() - 1;
        int c = 0;
        while (i >= 0 || j >= 0 || c == 1) {
            c += (i >= 0 ? a.charAt(i--) - '0' : 0);
            c += (j >= 0 ? b.charAt(j--) - '0' : 0);
            sum.insert(0, c % 2);
            c >>= 1;
        }
        return sum.toString();
    }

        /**
     * follow up:
     * 1.问了我为啥不用string做，用string做的时间复杂度是多少。
     * 我说n+(n-1)+...+1 = O(n^2)
     * 2.用了string相加的方法，被问到这么想加时间复杂度是多少。怎么更好，我说可以用StringBuilder，不过要return的时候要reverse先。
     * 3.为什么不用String而是StringBuilder？我说String需要每次拼接到最前面，复杂度是On。又问有没有比StringBuilder更好的？
     * 想了想说char数组，因为返回时可以不用reverse了。
     * 小哥接着问还有没有其他好处，这块卡住了，要hints，小哥说没事，告诉我因为StringBuilder需要扩容。

     * 4.改成5进制再加的结果
     */

StringBuilder 与 StringBuffer 的构造方法会创建一个默认大小是 16 的字符数组。使用 append() 方法时，如果长度超过了字符串存储空间大小就需要进行扩容，它会重新分配内存，创建一个更大的数组，这个数组的容量是原来的 2 倍 + 2 的大小，并将原先的数组复制过来，再丢弃旧的数组。因此，在大多数情况下，可以在创建 StringBuilder 与 StringBuffer 的时候指定大小，这样可以避免在容量不够的时候自动增长，从而提高性能。