Comment on page

67.Add-Binary

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"

代码

Approach #1 Built-in functions

class Solution {
public String addBinary(String a, String b) {
return Integer.toBinaryString(Integer.parseInt(a, 2) + Integer.parseInt(b, 2));
}
}

Approach #2 Bit-by-Bit Computation

Time && Space complexity: O(max(N,M)),
class Solution {
public String addBinary(String a, String b) {
int n = a.length(), m = b.length();
if (n < m) return addBinary(b, a);
int L = Math.max(n, m);
​
StringBuilder sb = new StringBuilder();
int carry = 0, j = m - 1;
for (int i = L - 1; i >= 0; i--) {
if (a.charAt(i) == '1') carry++;
if (j >= 0 && b.charAt(j--) == '1') carry++;
​
if (carry % 2 == 1) {
sb.append('1');
} else {
sb.append('0');
}
​
carry /= 2;
}
​
if (carry == 1) sb.append('1');
sb.reverse();
return sb.toString();
}
}