67. 二進制求和

思路

先把比較小的字串前面補零，直到長度相等。
從個位數開始，將兩個位置的數字相加，並記錄進位，把個位數加入res。
在遍歷結束之後，如果依舊有進位，就將1加入到res中，
最後將res反轉，就是答案。

程式碼

模擬

class Solution {
public:
    string addBinary(string a, string b) {
        if(a.length() < b.length()) swap(a, b); // 確保 a 比較長
        int diff = a.length() - b.length();
        b = string(diff, '0') + b;
        int n = a.length();
        int carry = 0, sum;
        string res;
        for(int i = n - 1; i >= 0; i--) {
            int x = a[i] - '0';
            int y = b[i] - '0';
            sum = (x + y + carry) % 2;
            carry = (x + y + carry) / 2;
            res += to_string(sum);
        }
        if(carry) res += '1';
        reverse(res.begin(), res.end());
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$