題目敘述 Add Binary
題目給定兩個二進位字串a, b
請計算a+b二進位加法的答案，最後以字串的形式輸出。
測試範例
Example 1:Input: a = "11", b = "1"
Output: "100"
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
約束條件
Constraints:
1 <= a.length, b.length <= 10^4
字串a 和 字串b的長度都介於 1個 ~ 一萬個字元。
aandbconsist only of'0'or'1'characters.
字串a 和 字串b只會包含'0'或'1'
- Each string does not contain leading zeros except for the zero itself.
前面沒有無意義的leading zero補零
演算法 模擬二進位加法
二進位加法過程
模擬二進位加法，逢二就進位，從最低位元逐項累加到最高位元。
0 + 0 = 0
0 + 1 = 1
1 + 0 = 0
1 + 1 = 0 ，同時傳遞進位1給左側的高位元
最後，以字串的形式輸出答案。
程式碼 模擬二進位加法
class Solution:
def addBinary(self, a: str, b: str) -> str:
result = ''
a = list(map(int, a))
b = list(map(int, b))
carry = 0
while a or b or carry:
digit_sum = 0
if a: digit_sum += a.pop()
if b: digit_sum += b.pop()
digit_sum += carry
carry, digit_sum = digit_sum // 2, digit_sum % 2
result = str(digit_sum) + result
return result
複雜度分析
時間複雜度:O(m+n)
總計算時間依賴於長度較長的那個字串，依然是線性時間演算法。
空間複雜度: O(m+n)
輸出總長度也依賴長度較長的那個字串，依然是線性空間演算法。
