【LeetCode】 67. Add Binary

Description

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Constraints:

• Each string consists only of '0' or '1' characters.
• 1 <= a.length, b.length <= 10^4
• Each string is either "0" or doesn't contain any leading zero.

給予兩個二進制字串，回傳他們的總和(也是一個二進制字串)。

輸入字串都不會是空的並且只包含1或0。

限制：

• 每個字串只包含0或1的字元。
• 1 <= a.length, b.length <= 10^4
• 每個字串除了"0"以外，不會有零在最前面的情況。

Example:

Example 1:

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


Example 2:

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

Solution

• 由限制條件第二點來看，可以知道這是一題大數運算的題目。
• 只是從一般的大數加法改為二進制，其他概念都一模一樣。
• 從最低位元相加，加完之後如果大於一，就減二並進位，一路加到最高位元。
  • 要注意輸入是string，因此取單個位元是char而不是int。
• 最後要注意最高位元的進位會出現錯誤，要先插入一個0在最前面才可以正常執行。

Code

class Solution {
public:
    string addBinary(string a, string b) {
        if(a.length() < b.length()) 
            return addBinary(b, a);
        
        for(int i = 0; i < a.length(); i++)
        {
            if(i < b.length())
                a[a.length() - i - 1] += b[b.length() - i - 1] - '0';
            
            if(i == a.length() - 1)
                if(a[0] > '1')
                    a.insert(a.begin(), '0');
            while(a[a.length() - i - 1] > '1')
            {
                a[a.length() - i - 1] -= 2;
                a[a.length() - i - 2] += 1;
            }
        }
        return a;
    }
};

tags: LeetCode C++