Python solution using hash maps, beats 95%


  • 0
    A

    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
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.