67.Add Binary

67.Add Binary

Given two binary strings a and b, return their sum as a binary string.

Example 1:

Input: a = “11”, b = “1”　　 Output: “100”

Example 2:

Input: a = “1010”, b = “1011”　　 Output: “10101”

題意是相加兩個binary string，回傳一個加好的binary string

要解決3個問題

1. 字串索引從左邊開始，但是binary是從右邊開始加
2. binary的進位
3. 各字元的計算

第1

從兩個字串的尾部開始像前面移動

每次都移動1，移動到 >= 0

0	1
1	1
0	1

以11和01互加會變成 001，所以會需要反轉

第2

一開始的進位是0

每次都要把此次的計算帶到下一次

並且進為大於0，代表計算還未結束

第3

字元的計算根據使用的程式語言會有所不同

1. 直接使用字元加
2. 轉成unicode的數字

Python Code

def addBinary(self, a: str, b: str) -> str:
  len_a = len(a)-1
  len_b = len(b)-1
  carry = 0 #紀錄進位
  binary = ""
  while len_a >= 0 or len_b >= 0 or carry > 0:
      _sum = carry 
      _sum += ord(a[len_a]) - 48 if len_a >= 0  else 0
      # 轉成 Unicode point - 48 就可以以整數0為基準
      # python 不能字串相減
      _sum += ord(b[len_b]) - 48 if len_b >= 0  else 0
      binary += str(_sum % 2)
      carry = _sum // 2
      len_a -= 1
      len_b -= 1

  return binary[::-1] #[start:end:step] 反轉字串