目標：
這題的目標在於講述簡單的字串操作方式，以及簡單的二進位的表示法。

原題：

Question:
Given two binary strings, return their sum (also a binary string).
The input strings are both non-empty and contain only characters 1 or 0.

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

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

分析/解題：
題目給定兩個二進位字串，試求其和(同樣以二進位字串表達)。
在電腦的世界裡，本質上是由0和1所構成的，因為對它來說，
最容易的表達方式就是電路的開路和斷路兩種狀態。
如果大家忘記二進位的表示方式，可以從wiki的說明大概回憶一下XD
這裡只要知道要轉為10進位的話，就是由右至左從2⁰開始相乘相加就對了。
例: 1010 -> 0 * 2⁰ + 1 * 2¹ + 0 * 2² + 1 * 2³ = 0 + 2 + 0 + 8 = 10
每個位數之間是2倍，每滿2就要向左邊進一位。

如果是C/C++/Java等規範相對嚴格的語言的話，
以Java為例，其int變數型態一般是用32-bit來儲存並且含有正負號，
也就是它只可以接受範圍在**-2³¹~2³¹-**1之間的數字，超過這個範圍即會overflow(溢位)，
這也是這個題目之所以會用字串表達的原因。
(不同的語言的int變數所涵蓋的範圍不一定相同)

Python就沒有這種限制，直譯器已經處理好很多事情了，
所以下面就會看到一些比較簡單(偷吃步)的做法。

對Java而言，我們既然擔心會溢位導致不能夠直接轉換，
那麼只好一位一位去做操作了。我們可以使用StringBuilder這個處理字串的類別，
從第0位開始將兩邊的數字相加，並且處理進位(carry)的部分。

對Java而言，字串(String)拆出來的每個單位叫字元(char)，
使用String.charAt(i)函式，可以將index i的字元拆解出來。
拆出來的字元其實已經可以用數字的形態印出了，
但它是代表ASCII code表上的位置，而非真的數字，
要得到它實際的數字的話，由於'0'~'9'在表上是連續的，
我們可以減去'0'的位置48，即可得到實際的數字；
或者記不了的話，直接拿該字元去減掉'0'，也可以得到相同的結果。
這樣的操作也適用於大小寫的英文字母上，請多留意。

那麼問題就簡單了: 只要是還有位數的狀況下，就取出字元減掉'0'，
否則就當作是0(代表另一個字串比較長)，最後比到兩邊長度都用完，
這時候StringBuilder應該沿路將所有位數從最低位組合到最高位了，
最後處理最高位有可能的進位後，只要再將其進行反轉(reverse)操作，
再轉為字串(toString)即可。

Java:

// Solution from lx223
public class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int i = a.length() - 1, j = b.length() - 1, carry = 0;
        while (i >= 0 || j >= 0) {
            int sum = carry;
            if (j >= 0) sum += b.charAt(j--) - '0';
            if (i >= 0) sum += a.charAt(i--) - '0';
            sb.append(sum % 2);
            carry = sum / 2;
        }
        if (carry != 0) sb.append(carry);
        return sb.reverse().toString();
    }
}

Python的部分相對簡單的多(可以偷吃步XD)，
只要將a跟b先轉成int，相加後再轉成二進位即可。
轉成int的作法是int(num, base)，
num表示你的字串，base表示這段字串的進位方式。
相加後轉成bin要特別注意Python的表達方式是以**’0b’**為開頭，
所以我們只保留index 2以後的部分。

Python:

class Solution:
    def addBinary(self, a: 'str', b: 'str') -> 'str':
        return bin(int(a, 2) + int(b, 2))[2:]

簡單吧!

面試實際可能會遇到的問題：
「時間複雜度？」( O(max(len(a), len(b))) )

「Python解是很簡單啦，但可以用一個一個比較的方法嗎？」
(請仿照Java的方式寫給他XD)
(補充: Python的ASCII和數字順序的互轉是 ord(c)跟 chr(a)，
前者字元轉數字，後者數字轉字元)

「(Java)j++和++j有什麼不同？」
(++本身是代表將這個值增加1，
而擺在變數後面代表這整行執行完畢以後，才進行遞增；
後者則代表先將自己本身增加1以後，才執行這整行的操作)

從LeetCode學演算法，我們下次見囉，掰~

下篇預告：
0070. Climbing Stairs (Easy)