###### tags: `Leetcode` `easy` `string` `python` `c++`

# 67. Add Binary

## [題目來源:] https://leetcode.com/problems/add-binary/

## 題目:
Given two binary strings a and b, return their sum as a binary string.

## 解題想法:
* 遞迴
* 每次判斷最尾巴字符 若1+1 需要進位

## Python(Sol1):

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        #法1: 超偷懶 return bin(int(a, 2) + int(b, 2))[2:]
        #法2:
        #判斷空字串 可以用一句:return a if a else b
        if not a:
            return b
        if not b:
            return a
        #從最後一位下手
        if a[-1]=='1' and b[-1]=='1':
            return self.addBinary(self.addBinary(a[:-1],b[:-1]),'1')+'0'
        elif a[-1]=='0' and b[-1]=='0':
            return self.addBinary(a[:-1],b[:-1])+'0'
        else:
            return self.addBinary(a[:-1],b[:-1])+'1'

if __name__ == '__main__':
    result = Solution()
    a = "111"
    b = "11"
    ans = result.addBinary(a,b)
    print(ans)
    

## Python(Sol2):

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        res=''
        #從尾巴開始加
        m=len(a)-1
        n=len(b)-1
        plus=0
        while m>=0 or n>=0 or plus:
            plus+= int(a[m]) if m>=0 else 0
            plus+= int(b[n]) if n>=0 else 0
            res+= str(plus%2)
            m-=1
            n-=1
            plus=plus//2
        return res[::-1]

## C++:

#include <iostream>
#include <algorithm>

using namespace std;

class Solution
{
public:
    string addBinary(string a, string b)
    {
        string res = "";
        int carry = 0, m = a.size() - 1, n = b.size() - 1;
        while (m >= 0 || n >= 0 || carry == 1)
        {
            // char into int: char-'0'
            carry += m >= 0 ? a[m] - '0' : 0;
            carry += n >= 0 ? b[n] - '0' : 0;
            // int into char: int+'0'
            res += (carry % 2 + '0');
            m -= 1;
            n -= 1;
            carry /= 2;
        }
        //需宣告新的變數存原始字串
        string re_res(res);
        // #include <algorithm>
        reverse(re_res.begin(), re_res.end());
        return re_res;
    }
};

int main()
{
    string a = "1010", b = "1011";
    Solution res;
    string ans = res.addBinary(a, b);
    cout << ans << endl;
    return 0;
}
/*
if (i<0)
    i=10;
else
    i=i-1;
=>> i= (i<0)? 10:i-1;
//判別式?true:false
*/