（ブログ記事からの転載）
[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な処理をしています。