LeetCode: 67-Add Binary 解題紀錄

Last Updated on 2022-01-10 by Clay

題目

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.

這題題目的意思很簡單。題目給定兩組輸入的字串，每個字串都是使用二進制表示的一個數字。我們要做的，就是將兩組以字串表示的二進制數字相加，並回傳二進制表示的字串解答。

---

解題方法

這個題目我的解法就是分別設定 ai 跟 bi 兩個索引，並依序遍歷兩組輸入字串，判斷兩個輸入的值，並存入一個名為 sum 的字串變數。

實際上還存在著對記憶體存取更優化的解題方法，比方說只取長度較長的那邊作為計算的基底，這樣就不用另外開一組 string。

但受限於時間，今天就只簡單地解掉這題就好。

時間複雜度

Time Complexity	O(n)
Space Complexity	O(n)

C++ 範例程式碼

class Solution {
public:
    string addBinary(string a, string b) {
        // Init
        string sum;
        int carry = 0;
        int ai = a.size()-1;
        int bi = b.size()-1;
        int temp = 0;
        
        // a + b
        while (ai >= 0 || bi >= 0 || carry) {
            // Compute temp value
            temp = carry;
            if (ai >= 0 && a[ai] == '1') ++temp;
            if (bi >= 0 && b[bi] == '1') ++temp;
            
            // Carry
            carry = temp / 2;
            
            // Add to "sum"
            temp = temp % 2;
            if (temp == 1) sum =  "1" + sum;
            else sum = "0" + sum;            
            
            // Step
            --ai;
            --bi;
        }
        
        // Answer
        return sum;
    }
};

Python 範例程式碼

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        # Init
        _sum = ""
        carry = 0
        ai = len(a) - 1
        bi = len(b) - 1
        temp = 0
        
        # a + b
        while ai >= 0 or bi >= 0 or carry:
            # Compute temp value
            temp = carry
            if ai >= 0 and a[ai] == '1': temp += 1
            if bi >= 0 and b[bi] == '1': temp += 1
            
            # Carry
            carry = temp // 2
            
            # Add to "sum"
            temp = temp % 2
            if temp == 1: _sum =  "1" + _sum
            else: _sum = "0" + _sum            
            
            # Step
            ai -= 1
            bi -= 1
        
        # Answer
        return _sum

---

References

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

---

Read More

• Clay-Technology World: LeetCode 解題紀錄