leetcode : Add Binary

runtime 0 ms, beats 100% of cpp submissions
O(m+n) solution with explanation

tags: string

🔗 link

Add Binary

📖 description

給定兩個 01 陣列 a、b ，請求將兩者相加乘新的字串回傳。

ex.
    Input: 
        a = "1010", b = "1011"

    Output: "10101"

🧠 solution

根據題意模擬一次計算，只需要注意額外處理進位其況即可。

⏳ time complexity

遍歷兩個字串，時間複雜度 O(m+n) ，其中 m, n 代表兩個字串的長度。
總時間複雜度 O(m+n)

📝 code

class Solution {
public:
    string addBinary(string a, string b) {
        reverse(a.begin(),a.end());     // 避免長度不同
        reverse(b.begin(),b.end());
        int n = max(a.size(),b.size());
        string ans = "";
        int carry = 0;
        int cnt = 0;
        for(int i=0;i<n;i++){
            int tmp = carry;
            if(i<a.size()){
                tmp+=a[i]-'0';
            }
            if(i<b.size()){
                tmp+=b[i]-'0';
            }
            if(tmp>=2){
                carry = 1;
                tmp-=2;
            }
            else{
                carry = 0;
            }
            ans+=tmp+'0';
        }
        if(carry == 1){  // 處理最高位進位
            ans+='1';
        }
        reverse(ans.begin(),ans.end());     // 轉回來
        return ans;
    }
};