My Iternative and Recursive solutions in Python


  • 0
    D
    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
            
                
    

Log in to reply
 

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