An accepted concise Python recursive solution 10 lines


  • 30
    L
    #add two binary from back to front, I think it is very self explained, when 1+1 we need a carry.
       class Solution:
            def addBinary(self, a, b):
                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[0:-1],b[0:-1]),'1')+'0'
                if a[-1] == '0' and b[-1] == '0':
                    return self.addBinary(a[0:-1],b[0:-1])+'0'
                else:
                    return self.addBinary(a[0:-1],b[0:-1])+'1'

  • 0
    R
    This post is deleted!

  • 2
    R

    I used Python with bitwise solution. It can be found on cc150.
    The solution does not calculate carry digit by digit but use and("&") operator, which means, if two digits are "1", there must be a carry equals 1. But we need to left shift("<<") it because the carry is one digit higher.
    for the part not include carry, we can use XOR(^), 1^1 = 0, 1 + 1 = 10, without carry ,it is also "0".

    class Solution:
        # @param a, a string
        # @param b, a string
        # @return a string
        def addBinary(self, a, b):
            if a == "":
                return b
            if b == "":
                return a
            a_2 = int(a,2)
            b_2 = int(b,2)
            carry = 1
            while carry != 0:
                carry = (a_2 & b_2)<<1
                a_2 = a_2 ^ b_2
                b_2 = carry
            return bin(a_2)[2:]

  • 7
    W

    I think you answer can be simplified to:
    return bin(int(a, 2) + int(b, 2))[2:]


  • 0
    F

    Doesn't you encounter the problem of reaching maximum depth of recursion?


  • 0
    F

    Oh, my bad, it doesn't. Nvmd


  • 2
    M

    Thank you for your sharing! I think it can be more concise like the following (Actually, it's really an awesome answer! ):

    class Solution:
        def addBinary(self, a, b):
            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[0:-1], b[0:-1]), '1') + '0'
            else:
                return self.addBinary(a[0:-1], b[0:-1]) + str(int(a[-1]) + int(b[-1]))

  • -1
    F

    @Meng-Ju I agree that the solution can be narrowed down to only three if statements, but I feel it would be better to take advantage of the fact that we can use bitwise operations:

        if len(a) == 0: return b
        if len(b) == 0: return a
        if int(a[-1]) & int(b[-1]):
            return self.addBinary(self.addBinary(a[0:-1], b[0:-1]), str(int(a[-1]) & int(b[-1]))) + str(int(a[-1]) ^ int(b[-1]))
        else:
            return self.addBinary(a[0:-1], b[0:-1]) + str(int(a[-1]) ^ int(b[-1]))

  • 0
    B

    @wenchao_hu
    it is cool

    at first, i use .repalce('0b', '') instead of [2:], it only beats 10%, i beat 75% when i use the latter..


  • 0
    Y

    How does it work when you put three arguments into two arguments functions?


  • 0
    L

    @yidong_w he used that function twice


  • 0
    A

    @wenchao_hu this may not be allowed in real interview


Log in to reply
 

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