Question

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"

Difficulty:Easy

Category:String

Analyze

这道题目需要设置两个指针分别在指向两个string的最后一位，然后在设置一个标志位carry, 每次如果最低位的和大约2的话，就carry = sum / 2得到需要进位的部分，继续指针左移，计算下一个，最后的时候，如果carry还没有为0, 那就在string res的前面加上1，就是1 + res。

Solution

Time complexity: O(max(len_a, len_b)) Space complexity: O(n)

class Solution {
 public:
  string addBinary(string a, string b) {
    string ans;
    int len_a = a.length() - 1, len_b = b.length() - 1;
    int carry = 0;
    while (len_a >= 0 || len_b >= 0) {
      int m = len_a >= 0 ? a[len_a--] - '0' : 0;
      int n = len_b >= 0 ? b[len_b--] - '0' : 0;

      int sum = m + n + carry;
      ans = to_string(sum % 2) + ans;
      carry = sum / 2;
    }
    return carry == 1 ? to_string(carry) + ans : ans;
  }
};