67. Add Binary

題目敘述

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 <= 10**4
• a and b consist only of '0' or '1' characters.
• Each string does not contain leading zeros except for the zero itself.

題目翻譯

有兩個 Binary 的字串 a 和 b，需要回傳其加總後的 Binary 字串。

解法解析

這題如果只是當純的將字串轉換成數值，很容易遇到一個問題就是會超出數值資料格式的範圍。可能就會需要使用到 BigInt 或類似 Long 的資料格式。所以比較好的方式是針對各個 Bit 作處理。

Bit-by-Bit Computation

這個解法很單純，就像是數值相加一樣，從個位數開始加，紀錄需要進位的值。

N 和 M 分別是 a 和 b 的字串長度 時間複雜度：O(max(N,M)) 空間複雜度：O(max(N,M))

Bit Manipulation

這解法主要使用了 Bitwise operator 來做處理。相加的話可以使用 XOR 來做處理，而是否需要進位的話則可以使用 AND 和 Left shift 來處理。但是這個解法就會需要 Big Int 或是 Long 的資料型態。所以如果程式語言沒有支援的話，就不適合使用此解法。

N 和 M 分別是 a 和 b 的字串長度 時間複雜度：O(N+M) 空間複雜度：O(max(N,M))

解法範例

Go

Bit-by-Bit Computation

func addBinary(a string, b string) string {
    i, j, res, carry := len(a)-1, len(b)-1, "", 0
    for i >= 0 || j >= 0 {
        if i >= 0 {
            carry += int(a[i] - '0')
            i--
        }
        if j >= 0 {
            carry += int(b[j] - '0')
            j--
        }
        res = strconv.Itoa(carry%2) + res
        carry /= 2
    }
    if carry == 1 {
        return "1" + res
    }
    return res
}

Bit Manipulation

func addBinary(a string, b string) string {
    var x, _ = new(big.Int).SetString(a, 2)
    var y, _ = new(big.Int).SetString(b, 2)

    var sum = new(big.Int)
    var carry = new(big.Int)
    for y.Text(2) != "0" {
        sum.Xor(x, y)
        carry.And(x, y).Lsh(carry, 1)
        x.Set(sum)
        y.Set(carry)
    }
    return x.Text(2)
}

JavaScript

Bit-by-Bit Computation

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function (a, b) {
    const N = a.length,
        M = b.length;
    let r = '';
    let carry = false;
    for (let i = 0; i < Math.max(N, M); i++) {
        const da = a[N - i - 1] === '1',
            db = b[M - i - 1] === '1';

        const sum = (da !== db) !== carry;
        r += (sum ? '1' : '0');
        carry = (da && carry) || (db && carry) || (da && db);
    }

    return carry ? `1${r}` : r;
};

Bit Manipulation

/**
 * @param {string} a
 * @param {string} b
 * @return {string}
 */
var addBinary = function (a, b) {
    return (BigInt(`0b${a}`) + BigInt(`0b${b}`)).toString(2);
};

Kotlin

PHP

Bit-by-Bit Computation

class Solution
{

    /**
     * @param String $a
     * @param String $b
     * @return String
     */
    function addBinary($a, $b)
    {
        $n = max(strlen($a), strlen($b));
        $a = str_pad($a, $n, '0', STR_PAD_LEFT);
        $b = str_pad($b, $n, '0', STR_PAD_LEFT);
        $carry = 0;
        $answer = array();
        for ($i = $n - 1; $i >= 0; $i--) {
            if ($a[$i] == '1') {
                $carry++;
            }
            if ($b[$i] == '1') {
                $carry++;
            }

            $answer[] = strval($carry % 2);
            $carry = floor($carry / 2);
        }

        if ($carry == 1) {
            $answer[] = '1';
        }
        $answer = array_reverse($answer);
        return implode('', $answer);
    }
}

Bit Manipulation

Python

Bit-by-Bit Computation

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        n = max(len(a), len(b))
        a, b = a.zfill(n), b.zfill(n)

        carry = 0
        answer = []
        for i in range(n - 1, -1, -1):
            if a[i] == '1':
                carry += 1
            if b[i] == '1':
                carry += 1

            answer.append(str(carry % 2))
            carry //= 2

        if carry == 1:
            answer.append('1')
        answer.reverse()
        return ''.join(answer)

Bit Manipulation

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            x, y = x ^ y, (x & y) << 1
        return bin(x)[2:]

Rust

Swift