给定两个二进制字符串，返回他们的和（用二进制表示）。

输入为非空字符串且只包含数字 1 和 0。

示例 1:

输入:

a = "11"
b = "1"

输出:

"100"

示例 2:

输入:

a = "1010"
b = "1011"

输出:

"10101"

C++

class Solution {
public:
    string addBinary(string a, string b) {
        int lena = a.length();
        int lenb = b.length();
        // cout << lena << ", " << lenb << endl;
        string res;
        int k=0,i=lena-1,j=lenb-1;
        string temp(1,'0');
        while(j>=0 && i>=0){
            // cout << "ss" << a[i]-'0'+b[j]-'0'+k <<endl;
            if(a[i]-'0'+b[j]-'0'+k == 2){
                k = 1;
                res.insert(0, temp);
                // cout << res << endl;
            }else{
                if(a[i]-'0'+b[j]-'0'+k == 3){
                    string s(1,'1');
                    res.insert(0, s);
                    k=1;
                }else{
                    char c = a[i]-'0'+b[j]-'0'+k +'0';
                    string s(1, c);
                    res.insert(0, s);
                    k=0;
                }
            }
            --i;--j;
        }
        int index = i>j?i:j;
        for(int i=index;i>=0;i--){
            if(lena>=lenb){
                if(a[i]-'0'+k == 2){
                    res.insert(0, temp);
                    k=1;
                }else{
                    string s(1, a[i]-'0'+k+'0');
                    res.insert(0, s);
                    k=0;
                }
                
            }else{
                if(b[i]-'0'+k == 2){
                    res.insert(0, temp);
                    k=1;
                }else{
                    string s(1, b[i]-'0'+k+'0');
                    res.insert(0, s);
                    k=0;
                }
            }
        }
        if(k == 1){
            string s(1,'1');
            res.insert(0, s);
        }
        return res;
    }
};