67.Add-Binary

67. Add Binary

题目地址

https://leetcode.com/problems/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();
  }
}