67. Add Binary

题目：

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

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

链接：  http://leetcode.com/problems/add-binary/

一刷，最简单的分两段计算。

class Solution(object):
    def addBinary(self, a, b):
        if not a:
            return b
        if not b:
            return a
        
        result = []
        common_length = min(len(a), len(b))
        carry = 0
        
        for idx in range(1, common_length + 1):
            carry, ret = (int(a[-idx]) + int(b[-idx]) + carry) / 2, (int(a[-idx]) + int(b[-idx]) + carry) % 2
            result.append(str(ret))
        
        rest = a if len(a) > common_length else b
        for idx in range(common_length + 1, len(rest) + 1):
            carry, ret = (int(rest[-idx]) + carry) / 2, (int(rest[-idx]) + carry) % 2
            result.append(str(ret))
        
        if carry:
            result.append(str(carry))
        result.reverse()
        return ''.join(result)

一次遍历，可以减少边界条件的分析

class Solution(object):
    def addBinary(self, a, b):

        if not a:
            return b
        if not b:
            return a
        
        result = []
        a_index = len(a) - 1
        b_index = len(b) - 1
        carry = 0
        
        while a_index >= 0 or b_index >= 0:
            a_val = int(a[a_index]) if a_index >= 0 else 0
            b_val = int(b[b_index]) if b_index >= 0 else 0
            carry, ret = (a_val + b_val + carry) / 2, (a_val + b_val + carry) % 2
            result.append(str(ret))
            a_index -= 1
            b_index -= 1

        if carry:
            result.append(str(carry))
        result.reverse()
        return ''.join(result)

2/12/2017, Java, 无脑乱刷。非常需要改进

错误

1. StringBuilder的各种方法：setLength(), setCharAt(), append()

2. 判断第一次相加是否为0，初始条件判断缺失，不但在2个相加时，最后只剩下一个String的时候第一次也需要判断

3. char没有int(char)这种方法，只能通过char - '0'来判断

public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder ret = new StringBuilder();
        ret.setLength(Math.max(a.length(), b.length()));
        int sum;
        int carry = 0;
        int i = a.length() - 1, j = b.length() - 1;
        
        for(;i >= 0 && j >= 0;i--, j--) {
            sum = a.charAt(i) - '0' + b.charAt(j) - '0' + carry;
            if (sum == 0) {
                ret.setCharAt(Math.max(i, j), '0');
                carry = 0;
            } else if (sum == 1) {
                ret.setCharAt(Math.max(i, j), '1');
                carry = 0;
            } else if (sum == 2) {
                ret.setCharAt(Math.max(i, j), '0');
                carry = 1;
            } else {
                ret.setCharAt(Math.max(i, j), '1');
                carry = 1;
            }
        }
        for(; i >= 0; i--) {
            sum = a.charAt(i) - '0' + carry;
            if (sum == 0) {
                ret.setCharAt(i, '0');
                carry = 0;
            } else if (sum == 1) {
                ret.setCharAt(i, '1');
                carry = 0;
            } else {
                ret.setCharAt(i, '0');
                carry = 1;                
            }
        }
        for(; j >= 0; j--) {
            sum = b.charAt(j) - '0' + carry;
            if (sum == 0) {
                ret.setCharAt(j, '0');
                carry = 0;
            } else if (sum == 1) {
                ret.setCharAt(j, '1');
                carry = 0;
            } else {
                ret.setCharAt(j, '0');
                carry = 1;                
            }
        } 
        if (carry != 0) {
            StringBuilder ret1 = new StringBuilder("1");
            ret1.append(ret);
            return ret1.toString();
        }
        return ret.toString();
    }
}