67. Add Binary

發表於 | 分類於

problem

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    string addBinary(string a, string b) {
        int n =a.size(), m = b.size();
        int len = max(n,m);
        if(n<m) a = string(m-n,'0') + a;
        if(n>m) b = string(n-m, '0') +b;
        int carry = 0;
        n = len-1, m = len-1;
        string ret;
        while(n>-1 || m>-1 || carry){
            int sum = carry;
            if(n>-1) sum+=a[n--]-'0';
            if(m>-1) sum+=b[m--]-'0';
            carry = sum/2;
            ret = to_string(sum%2)+ret;
        }
        return ret;
    }
};

analysis

  • time complexity O(n)
  • space complexity O(n)