I figured the most costly operation would be str to int operations so to avoid the conversion I created a hashmap of the truth table:

`(Carry, MSB, LSB) : (MSB, LSB)`

```
class Solution(object):
def addBinary(self, a, b):
"""
:type a: str
:type b: str
:rtype: str
"""
# hashmap of truth table
m = {
('0','0','0'): ('0','0'),
('0','0','1'): ('0','1'),
('0','1','0'): ('0','1'),
('0','1','1'): ('1','0'),
('1','0','0'): ('0','1'),
('1','0','1'): ('1','0'),
('1','1','0'): ('1','0'),
('1','1','1'): ('1','1'),
}
# initialize return str
r = ''
# eqalize the length of strings
# "11", "1" will become "11", "01"
if len(a) > len(b):
b = '0'*(len(a)-len(b)) + b
elif len(a) < len(b):
a = '0'*(len(b)-len(a)) + a
# Initial MSB, LSB is 0, 0
t = ('0','0')
for i in range(1,len(a)+1):
t = m[t[0],a[-i],b[-i]]
r = t[1] + r
# if MSB is not 0, we have a carry and we need to add it
if '0' not in t[0]:
r = t[0] + r
return r
```