右から左へのビット加算 による O(max(m,n)) 実装
2つの二進数文字列
a と
b
が与えられます。これらを加算し、結果を二進数文字列として返します。
例1:
入力: a = "11", b = "1"
出力: "100"
説明: 11 (3) + 1 (1) = 100 (4)例2:
入力: a = "1010", b = "1011"
出力: "10101"
説明: 1010 (10) + 1011 (11) = 10101 (21)1 <= a.length, b.length <= 10⁴
a と
b は
'0' または
'1'
のみで構成される
時間計算量: O(max(m, n))
m と n はそれぞれ文字列 a と b の長さ。各桁を1回ずつ処理します。
空間計算量: O(max(m, n))
結果の文字列は最大で max(m, n) + 1 の長さになります。
class Solution:
def addBinary(self, a: str, b: str) -> str:
result = []
carry = 0
i, j = len(a) - 1, len(b) - 1
# 右から左へ各桁を処理
while i >= 0 or j >= 0 or carry:
# 現在の桁の値を取得（範囲外は0）
digit_a = int(a[i]) if i >= 0 else 0
digit_b = int(b[j]) if j >= 0 else 0
# 現在の桁の合計 = digit_a + digit_b + carry
total = digit_a + digit_b + carry
# 結果の桁を追加（total % 2）
result.append(str(total % 2))
# 次の桁へのキャリーを計算（total // 2）
carry = total // 2
# インデックスを左に移動
i -= 1
j -= 1
# 結果を反転して返す（右から左に構築したため）
return ''.join(reversed(result))
フローの説明：
1. 初期化:
結果配列、キャリー、インデックス（i, j）を初期化
2. ループ条件: i または j
が0以上、またはキャリーがある間繰り返す
3. 桁の値取得:
各文字列から現在の桁の値を取得（範囲外は0）
4. 合計計算: digit_a + digit_b + carry
を計算
5. 結果追加: total % 2
を結果配列に追加
6. キャリー更新: total // 2
を次のキャリーとして保存
7. インデックス更新: i と j
をデクリメント
8. ループバック: 次の桁へ戻る
9. 結果反転:
右から左に構築したため、結果を反転して返す
| 指標 | 本実装（ビット加算） | 代替手法（整数変換） |
|---|---|---|
| 時間計算量 | O(max(m, n)) | O(m + n) |
| 空間計算量 | O(max(m, n)) | O(max(m, n)) |
| 実装の複雑さ | 中程度（キャリー処理が必要） | 簡単（組み込み関数使用） |
| 大きな数への対応 | ◎ 任意の長さ対応 | △ 整数オーバーフローの可能性 |
| 推奨度 | ★★★★★ 最適 | ★★☆☆☆ 小さい数のみ |
reversed()
は効率的にイテレータを返す