```
class Solution(object):
# Recursive approach O(n) with memory O(n) 72 ms.
# I think this is briliant solution but less space & time efficient than addBinary()
def addBinary2(self, a, b):
# base case
if len(a) == 0: return b
if len(b) == 0: return a
if a[-1] == b[-1] == '1':
return self.addBinary2(self.addBinary2(a[0:-1], b[0:-1]), '1') + '0'
elif a[-1] == b[-1] == '0':
return self.addBinary2(a[0:-1], b[0:-1]) + '0'
else:
return self.addBinary2(a[0:-1], b[0:-1]) + '1'
# Single pass O(n) without memory, n = length of longer string 62 ms
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
longer = a if len(a) > len(b) else b
shorter = b if len(b) < len(a) else a
n, m, carry = len(shorter)-1, len(longer)-1, 0
s = ''
while m >= 0:
if n == -1:
break
if shorter[n] == longer[m] == '1':
s = str(carry) + s
carry = 1
elif shorter[n] == longer[m] == '0':
s = str(carry) + s
carry = 0
else:
if carry:
s = '0' + s
else:
s = '1' + s
carry = 0
m -= 1
n -= 1
while m >= 0:
if longer[m] == '1':
if carry:
s = '0' + s
else:
s = '1' + s
carry = 0
else:
if carry:
s = '1' + s
carry = 0
else:
s = '0' + s
m -= 1
if carry:
s = '1' + s
return s
```