0067. Add Binary - chasel2361/leetcode GitHub Wiki

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.

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

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

python可以用非常偷吃步的方法，直接把string轉換成int相加，再轉換成binary輸出就好

[1] int(obj, base)：base指的是obj的進位方式，此處應指定為2
[2] bin函式輸出的值會帶有'0b'標記，需要將它去除

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

這樣的時間複雜度應該是O(1)，所以超級快XD

那如果不用偷吃步的話要怎麼解決呢？

利用遞迴法可以簡單的解決進位問題，只要判斷相加的結果以及逐步手動進位就可以了

[1] 當 a, b 都還存在時，判斷兩者是 0+0 、 1+1 ，或 1 + 0
[2] 0 + 0 = 0，不須進位，手動進位一次
[3] 1 + 1 = 10，手動進位兩次
[4] 1 + 0 = 1，手動進位一次

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        if not a:
            return b
        if not b:
            return a
            
        if a[-1] == '0' and b[-1] == '0':  # [1]
            return self.addBinary(a[:-1], b[:-1]) + '0'  # [2]
        elif a[-1] == '1' and b[-1] == '1':  # [1]
            return self.addBinary(self.addBinary(a[:-1], b[:-1]), '1') + '0'  # [3]
        else:  # [1]
            return self.addBinary(a[:-1], b[:-1]) + '1'  # [4]

這個寫法比較腳踏實地一點，不過時間複雜度就上升到O(N)，雖然要遞迴很多層但應該還算快(吧)