67. Add Binary

LeetCode 67. Add Binary

Description

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"

Constraints:

• 1 <= a.length, b.length <= 104

• a and b consist only of '0' or '1' characters.

• Each string does not contain leading zeros except for the zero itself.

Tags

Math, String

Solution

本题与LeetCode 415. Add Strings极为相似，都是倒序遍历字符串且终止条件是任一指针不越界或进位不为0，只是进位条件上有所区别。

This question is quite similar to LeetCode 415. Add Strings, and only the conditions to produce the carry bit are different. See Reference section.

Complexity

• Time complexity: $O(n)$, n for the length of the longer string;

• Space complexity: $O(1)$, space for result is not considered.

Code

func addBinary(a string, b string) string {
	var ans []byte
	for i, j, c := len(a)-1, len(b)-1, 0; i >= 0 || j >= 0 || c != 0; i, j = i-1, j-1 {
		res := c
		if i >= 0 {
			res += int(a[i] - '0')
		}
		if j >= 0 {
			res += int(b[j] - '0')
		}
		switch res {
		case 0, 1:
			ans = append([]byte{byte(res + '0')}, ans...)
			c = 0
		case 2, 3:
			ans = append([]byte{byte(res - 2 + '0')}, ans...)
			c = 1
		}
	}
	return string(ans)
}

Reference

1. 415. Add Strings