分析

• 本题的考点：高精度加法。

• 直接使用加法的规则模拟一遍即可。为了处理方便，让个位在数组最低位。

代码

• C++

class Solution {
public:
    string addBinary(string a, string b) {

        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        string res;
        for (int i = 0, t = 0; i < a.size() || i < b.size() || t; i++) {
            if (i < a.size()) t += a[i] - '0';
            if (i < b.size()) t += b[i] - '0';
            res += to_string(t % 2);
            t /= 2;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

• Java

class Solution {
    public String addBinary(String a, String b) {

        char[] ca = new StringBuilder(a).reverse().toString().toCharArray();
        char[] cb = new StringBuilder(b).reverse().toString().toCharArray();

        StringBuilder sb = new StringBuilder();
        for (int i = 0, t = 0; i < ca.length || i < cb.length || t != 0; i++) {
            if (i < ca.length) t += ca[i] - '0';
            if (i < cb.length) t += cb[i] - '0';
            sb.append((char)(t % 2 + '0'));
            t /= 2;
        }
        sb = sb.reverse();
        return sb.toString();
    }
}

时空复杂度分析

• 时间复杂度：$O(n)$，n为字符串长度。

• 空间复杂度：考虑输出 $O(n)$。