LeetCode / Add Binary

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

Given two binary strings, return their sum (also a binary string).

The input strings are both non-empty and contains only characters 1 or 0.

Example 1:
Input: a = "11", b = "1"
Output: "100"

Example 2:
Input: a = "1010", b = "1011"
Output: "10101"

Add Binaryのタイトルの通り、Binaryの足し算です。
解けるは解けるんですが、如何にエレガントなアルゴリズムを書けるかが、コーディングインタビューでは見られるんだろうと思います。

解答・解説

解法1

まずは私の超力技のコードを示します。
いやー、見れば見るほど恥ずかしいんですが、あとで振り返ったときにこういう状態から来たんだ、と思えるように。

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        num = BinarytoInteger(a) + BinarytoInteger(b)
        ans = ''
        while num > 1:
            ans += str(num % 2)
            num = num // 2
        ans += str(num)
        ans = ''.join(list(reversed(ans)))
        return ans

def BinarytoInteger(a):
    return sum([int(e)*2**(len(a)-1-i) for i,e in enumerate(a)])

解法2

さて、ここからが本番です。。。
recursiveを使った、エレガントな解法が以下の通り。

class Solution:
    def addBinary(self, a: str, b: str) -> str:
        if len(a)==0: return b
        if len(b)==0: return a
        # 下１桁が両方1のときは、その桁は0となり1繰り上がる
        if a[-1] == '1' and b[-1] == '1':
            return self.addBinary(self.addBinary(a[0:-1],b[0:-1]),'1')+'0'
        # 下１桁が両方0のときは、その桁は0となる
        if a[-1] == '0' and b[-1] == '0':
            return self.addBinary(a[0:-1],b[0:-1])+'0'
        # 下１桁が片方0、片方1のときは、その桁は1となる
        else:
            return self.addBinary(a[0:-1],b[0:-1])+'1'

加算する2つの数の下１桁に注目し、3つの分岐で処理しています。
一番下の桁を処理したら下から２番目の桁、これを処理した下から３番目の桁、と順に遡っていくrecursiveな処理をしています。