> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/math/jia-fa/add-binary.md).

# 67. Add Binary

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"
```

**Constraints:**

* Each string consists only of `'0'` or `'1'` characters.
* `1 <= a.length, b.length <= 10^4`
* Each string is either `"0"` or doesn't contain any leading zero.

## Thoughts

和Add String基本一样, 只是这里是二进制.

## Code

```java
class Solution:
    def addBinary(self, a: str, b: str) -> str:
        i, j, c, res = len(a) - 1, len(b) - 1, 0, ''
        while i >= 0 or j >= 0 or c > 0:
            ca = cb = 0
            if i >= 0: ca = 1 if a[i] == '1' else 0
            if j >= 0: cb = 1 if b[j] == '1' else 0
            res += str((ca + cb + c) % 2)
            c = 1 if ca + cb + c >= 2 else 0
            i -= 1
            j -= 1
        return res[::-1]
    
```

```java
class Solution {
    public String addBinary(String a, String b) {
        StringBuilder sb = new StringBuilder();
        int carry = 0;
        for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0 || carry > 0; i--, j--) {
            int ai = i >= 0 ? a.charAt(i) - '0': 0;
            int bi = j >= 0 ? b.charAt(j) - '0': 0;
            int sum = ai + bi + carry;
            carry = sum > 1 ? 1 : 0;
            sb.insert(0, sum % 2);
        }

        return sb.toString();
    }
}
```

## Analysis

时空复杂度O(N).