給定兩個二進位字串
a和b，回傳它們的和（也是二進位字串）。
Example:
Input: a = “1010”, b = “1011” Output: “10101”
Intuition
TIP
核心思路：模擬二進位加法——從最低位開始逐位相加，處理進位。
- 與十進位加法相同的邏輯，只是基數從 10 變為 2
- 從兩個字串的末尾同時開始，逐位相加
- 每位的結果 =
(a_bit + b_bit + carry) % 2，進位 =(a_bit + b_bit + carry) / 2
Approaches
⭐ 1. Simulate Binary Addition — O(max(m, n)) / O(max(m, n))
- Idea: 雙指標從末尾開始，逐位計算和與進位
- Time:
O(max(m, n))- m, n 為兩字串長度 - Space:
O(max(m, n))- 結果字串
class Solution {
fun addBinary(a: String, b: String): String {
val sb = StringBuilder()
var i = a.length - 1
var j = b.length - 1
var carry = 0
while (i >= 0 || j >= 0 || carry > 0) {
var sum = carry
if (i >= 0) {
sum += a[i] - '0'
i--
}
if (j >= 0) {
sum += b[j] - '0'
j--
}
sb.append(sum % 2)
carry = sum / 2
}
return sb.reverse().toString()
}
}2. Bitwise (no addition) — O(max(m, n)) / O(max(m, n))
- Idea: 用 XOR 做不進位加法，AND + 左移做進位計算，重複直到無進位。需用 BigInteger 處理大數
- Time:
O(max(m, n))- 最多迭代 max(m,n) 次 - Space:
O(max(m, n))
import java.math.BigInteger
class Solution {
fun addBinary(a: String, b: String): String {
var x = BigInteger(a, 2)
var y = BigInteger(b, 2)
while (y != BigInteger.ZERO) {
val sum = x.xor(y) // 不進位加法
val carry = x.and(y).shiftLeft(1) // 進位
x = sum
y = carry
}
return x.toString(2)
}
}🔑 Takeaways
- Pattern: 大數加法模板——從低位到高位逐位處理，適用於任何進位制
- Key trick:
sum % 2取當前位、sum / 2取進位；記得處理最後一個 carry