67. Add Binary

https://leetcode.com/problems/add-binary/description/

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

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]
    

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).