题目描述

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

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

样例

示例 1:
输入: a = "11", b = "1"
输出: "100"

示例 2:
输入: a = "1010", b = "1011"
输出: "10101"

算法1

(模拟) $O(n)$

模拟加法竖式。

时间复杂度

遍历两个字符串，总时间复杂度$O(n)$

参考文献

C++ 代码

class Solution {
public:
    string addBinary(string a, string b) {
        int m = a.size(), n = b.size();
        if (m < n) return addBinary(b, a);

        int carry = 0, i = m - 1, j = n - 1;
        string res;
        while(j >= 0){
            int num = (a[i--] - '0') + (b[j--] - '0') + carry;
            carry = num / 2;
            res.push_back(num % 2 + '0');
        }

        while(i >= 0){
            int num = (a[i--] - '0') + carry;
            carry = num / 2;
            res.push_back(num % 2 + '0');
        }

        if (carry) res.push_back(carry % 2 + '0');
        return string(res.rbegin(), res.rend());
    }
};

也可以精简一下

class Solution {
public:
    string addBinary(string a, string b) {
        int m = a.size(), n = b.size();
        if (m < n) return addBinary(b, a);

        int carry = 0, i = m - 1, j = n - 1;
        string res;
        while(j >= 0 || i >= 0 || carry){
            int num1 = i >= 0 ? a[i--] - '0' : 0;
            int num2 = j >= 0 ? b[j--] - '0' : 0;
            int num = num1 + num2 + carry;
            carry = num / 2;
            res.push_back(num % 2 + '0');
        }

        return string(res.rbegin(), res.rend());
    }
};