LeetCode 67：二進制字符串相加（模擬手算法）

題目描述

給定兩個二進制字符串，返回它們的和（也是二進制字符串）。例如 "11" + "1" = "100"。

解題思路

從字符串末尾向前逐位相加，維護進位。類似手算加法：對應位相加加上進位，結果位為和模 2，新進位為和除以 2。最後若有進位則補在最高位。

代碼實現 (C++)

class Solution {
public:
    string addBinary(string a, string b) {
        int i = a.size() - 1, j = b.size() - 1, carry = 0;
        string res;
        while (i >= 0 || j >= 0 || carry) {
            int sum = carry;
            if (i >= 0) sum += a[i--] - '0';
            if (j >= 0) sum += b[j--] - '0';
            res.push_back('0' + (sum & 1));
            carry = sum >> 1;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

複雜度

• 時間：O(max(m, n))，m、n 為字符串長度。
• 空間：O(max(m, n))，存儲結果。