67. Add Binary

problem description

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

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

algorithm thought

和十进制加法没什么不同，都是定义一个进位标志位，两数相加再加上标志位。得到的结果就是这一位，改变标志位。最后注意开头的0需要删除

code

class Solution {
public:
    string addBinary(string a, string b) {
        int al=a.size(),bl=b.size();
        string res=string(max(al,bl)+1,'0');
        if(al<bl){
           a=string(bl-al,'0')+a; 
        }
        else
            b=string(al-bl,'0')+b;
        int c=0;
        //cout<<a<<b;
        int count;
        for(int i=res.size()-2;i>=0;i--){
            count=int(a[i]-'0')+int(b[i]-'0')+c;
            if(count==1||count==3){
                res[i+1]='1';
            }
            if(count>=2){
              c=1;  
            }
            else
                c=0;
            //cout<<' '<<count;
        }
        res[0]=char(c+'0');
        
        count=0;
        while(res[count]=='0'){
            count++;
        }
        
        res=res.substr(count);
        
        return (res.size()==0?"0":res);
        
    }
};

algorithm analysis

线性处理两个字符串，最后时间复杂度O(n)