Given two binary strings, return their sum (also a binary string). The input strings are both non-empty and contains only characters1or 0.
Example 1:
Input: a = "11", b = "1"
Output: "100"
Example 2:
Input: a = "1010", b = "1011"
Output: "10101"
Solution 1: loop from right to left iteratively
def addBinary(a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
m = len(a) - 1
n = len(b) - 1
ret = ''
count = 0
while m >= 0 or n >= 0:
if m < 0:
temp = int(b[n]) + count
elif n < 0:
temp = int(a[m]) + count
else:
temp = int(a[m]) + int(b[n]) + count
if temp >= 2:
ret = str(temp - 2) + ret
count = 1
else:
ret = str(temp) + ret
count = 0
m -= 1
n -= 1
if count == 1:
ret = str(count) + ret
return ret
Solution 2: recursively
def addBinary(a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
if len(a) == 0:
return b
if len(b) == 0:
return a
if a[-1] == "1" and b[-1] == "1":
return self.addBinary(self.addBinary(a[:-1],b[:-1]),'1') + '0'
if a[-1] == '0' and b[-1] == "0":
return self.addBinary(a[:-1],b[:-1])+'0'
else:
return self.addBinary(a[:-1],b[:-1])+'1'