Question: https://oj.leetcode.com/problems/add-binary/

Question Name: Add Binary

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | class Solution: # @param a, a string # @param b, a string # @return a string def addBinary(self, a, b): # Make sure a is no longer than b. if len(a) > len(b): a, b = b, a aLen, bLen = len(a), len(b) # Addition for letters with carry addition = {"0": {"0":{"0":["0", "0"], "1":["1", "0"]}, "1":{"0":["1", "0"], "1":["0", "1"]}}, "1": {"0":{"0":["1", "0"], "1":["0", "1"]}, "1":{"0":["0", "1"], "1":["1", "1"]}} } result = "" # Add a and b[-aLen:] carry = "0" for index in xrange(-1, -aLen-1, -1): temp, carry = addition[a[index]][b[index]][carry] result = temp + result # Process the remaining part of b for index in xrange(-aLen-1, -bLen-1, -1): temp, carry = addition["0"][b[index]][carry] result = temp + result if carry == "0": # No carry at current digit. Then no change will # happen to the remaining part of b. result = b[:index] + result break else: if carry == "1": result = "1" + result return result |