[演算法題目] Add Binary

本題資訊

難度：easy
使用語言：C++
相關概念：String

題目敘述

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

Input:

a = "11", b = "1"

Output:

"100"

Idea

這題其實就是把二進位的過程搬到程式碼實現而已，另外還要稍微注意字串和整數的轉換，不論是 input 或是 output 都是字串。

一般來說都會從最後一個位數開始運算，我這裡希望後續處理方便，所以將整個字串反轉，這樣就可以從頭開始輪。並且在最後加入 result 時將數字附加在開頭。

運算的過程利用餘數和除法，一步步將每個位數算出來。並且利用 '0' 在字元和整數型態互轉（因為只有 0-9，和英文字母的處理一樣很好用）

#include <algorithm>

using namespace std;

string addBinary(string a, string b) {
  string result;
  int tmp = 0, n;
  
  reverse(a.begin(), a.end());
  reverse(b.begin(), b.end());
  n = a.size() > b.size() ? a.size() : b.size();
  
  for (int i = 0; i < n; i++){
    int a_i = i < a.size() ? a[i] - '0' : 0;
    int b_i = i < b.size() ? b[i] - '0' : 0;
    int value = (a_i + b_i + tmp) % 2;
    tmp = (a_i + b_i + tmp) / 2;
    
    result.insert(result.begin(), value + '0');
  }
  if (tmp == 1){
    result.insert(result.begin(), '1');
  }
  return result;
}

時間複雜度：\(O(n)\)，\(n\) 是 a 和 b 中最大長度。
空間複雜度：\(O(1)\)