67. Add Binary

📋 Đề Bài

Given two binary strings a and b, return their sum as a binary string.

Example 1:

Input: a = "11", b = "1"
Output: "100"

Example 2:

Input: a = "1010", b = "1011"
Output: "10101"

Constraints:

1 <= a.length, b.length <= 10⁴
a and b consist only of '0' or '1' characters.
Each string does not contain leading zeros except for the zero itself.

🧠 Thuật Toán & Kỹ Thuật

String (Chuỗi)

⏱️ Thời gian O(n)

💾 Không gian O(1)

💻 Lời Giải

C++ 0067-add-binary.cpp

class Solution {
public:
    string addBinary(string a, string b) {
        int carry = 0;
        int n = a.size(), m = b.size();
        int i = n - 1, j = m - 1;  
        string ans = "";
        while (i >= 0 || j >= 0 || carry) {
            int temp = carry;
            if (i >= 0) {
                temp += a[i] - '0';
                i--;
            }
            if (j >= 0) {
                temp += b[j] - '0';
                j--;
            }
            carry = temp / 2;
            ans.push_back(temp % 2 + '0');
        }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};