Add Binary

题目描述

Given two binary strings, return their sum (also a binary string).

For example, a = "11" b = "1" Return "100".

解题方法

从后往前不断地加，其实有点像merge two list。。。

Solution

class Solution(object):
    def addBinary(self, a, b):
        """
        :type a: str
        :type b: str
        :rtype: str
        """
        if not a:
            return b
        if not b:
            return a
        result = ""
        carry = 0
        lengthA = len(a)
        lengthB = len(b)
        p1 = lengthA - 1
        p2 = lengthB - 1
        while p1 >= 0 and p2 >= 0:
            curSum = int(a[p1]) + int(b[p2]) + carry
            if curSum == 0:
                result = "0" + result
                carry = 0
            elif curSum == 1:
                result = "1" + result
                carry = 0
            elif curSum == 2:
                result = "0" + result
                carry = 1
            elif curSum == 3:
                result = "1" + result
                carry = 1
            p1 -= 1
            p2 -= 1
        while p1 >= 0:
            curSum = int(a[p1]) + carry
            if curSum == 0:
                result = "0" + result
                carry = 0
            elif curSum == 1:
                result = "1" + result
                carry = 0
            elif curSum == 2:
                result = "0" + result
                carry = 1
            elif curSum == 3:
                result = "1" + result
                carry = 1
            p1 -= 1
        while p2 >= 0:
            curSum = int(b[p2]) + carry
            if curSum == 0:
                result = "0" + result
                carry = 0
            elif curSum == 1:
                result = "1" + result
                carry = 0
            elif curSum == 2:
                result = "0" + result
                carry = 1
            elif curSum == 3:
                result = "1" + result
                carry = 1
            p2 -= 1

        if carry == 1:
            result = "1" + result

        return result

Reference