LeetCode 67: Add Binary (Two-Pointer Carry Simulation)
LeetCode 67StringSimulationToday we solve LeetCode 67 - Add Binary.
Source: https://leetcode.com/problems/add-binary/
English
Problem Summary
Given two binary strings a and b, return their sum as a binary string.
Key Insight
This is exactly grade-school addition in base 2. Scan from right to left, maintain carry, append current bit, and reverse at the end.
Brute Force and Limitations
Converting to integers and adding looks simple, but can overflow for very long strings and is language-dependent for large numeric ranges.
Optimal Algorithm Steps (Right-to-Left Simulation)
1) Set pointers at the end of both strings.
2) While either pointer is valid or carry != 0, sum current bits + carry.
3) Append sum % 2, update carry = sum / 2.
4) Move pointers left, then reverse accumulated characters.
Complexity Analysis
Time: O(max(m, n)).
Space: O(max(m, n)) for output buffer.
Common Pitfalls
- Forgetting the final carry (e.g. "1" + "1" = "10").
- Mixing character codes with numeric values.
- Building string by prepending each step, causing extra overhead.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public String addBinary(String a, String b) {
int i = a.length() - 1;
int j = b.length() - 1;
int carry = 0;
StringBuilder sb = new StringBuilder();
while (i >= 0 || j >= 0 || carry != 0) {
int sum = carry;
if (i >= 0) sum += a.charAt(i--) - '0';
if (j >= 0) sum += b.charAt(j--) - '0';
sb.append(sum % 2);
carry = sum / 2;
}
return sb.reverse().toString();
}
}func addBinary(a string, b string) string {
i, j := len(a)-1, len(b)-1
carry := 0
out := make([]byte, 0, max(len(a), len(b))+1)
for i >= 0 || j >= 0 || carry != 0 {
sum := carry
if i >= 0 {
sum += int(a[i] - '0')
i--
}
if j >= 0 {
sum += int(b[j] - '0')
j--
}
out = append(out, byte('0'+sum%2))
carry = sum / 2
}
for l, r := 0, len(out)-1; l < r; l, r = l+1, r-1 {
out[l], out[r] = out[r], out[l]
}
return string(out)
}
func max(x, y int) int {
if x > y {
return x
}
return y
}class Solution {
public:
string addBinary(string a, string b) {
int i = (int)a.size() - 1;
int j = (int)b.size() - 1;
int carry = 0;
string out;
while (i >= 0 || j >= 0 || carry) {
int sum = carry;
if (i >= 0) sum += a[i--] - '0';
if (j >= 0) sum += b[j--] - '0';
out.push_back(char('0' + (sum % 2)));
carry = sum / 2;
}
reverse(out.begin(), out.end());
return out;
}
};class Solution:
def addBinary(self, a: str, b: str) -> str:
i, j = len(a) - 1, len(b) - 1
carry = 0
out = []
while i >= 0 or j >= 0 or carry:
total = carry
if i >= 0:
total += ord(a[i]) - ord('0')
i -= 1
if j >= 0:
total += ord(b[j]) - ord('0')
j -= 1
out.append(str(total % 2))
carry = total // 2
return ''.join(reversed(out))/**
* @param {string} a
* @param {string} b
* @return {string}
*/
var addBinary = function(a, b) {
let i = a.length - 1;
let j = b.length - 1;
let carry = 0;
const out = [];
while (i >= 0 || j >= 0 || carry) {
let sum = carry;
if (i >= 0) sum += a.charCodeAt(i--) - 48;
if (j >= 0) sum += b.charCodeAt(j--) - 48;
out.push(String(sum % 2));
carry = Math.floor(sum / 2);
}
return out.reverse().join('');
};中文
题目概述
给定两个二进制字符串 a 和 b，返回它们的二进制和（字符串形式）。
核心思路
本质就是“二进制竖式加法”。从右往左遍历，维护进位 carry，每轮产生当前位，最后反转结果。
基线解法与不足
把字符串转整数再相加在小输入下可行，但长字符串会溢出，而且不同语言大整数处理方式不同，不够稳健。
最优算法步骤（双指针 + 进位模拟）
1）两个指针分别指向 a、b 尾部。
2）循环条件是“任一指针未越界或仍有进位”。
3）累加当前位与进位，写入 sum % 2，更新 carry = sum / 2。
4）指针左移，最后反转输出。
复杂度分析
时间复杂度：O(max(m, n))。
空间复杂度：O(max(m, n))（结果缓冲）。
常见陷阱
- 忘记处理最后一位进位（例如 "1" + "1"）。
- 字符与数字转换写错（如直接相加字符码）。
- 每轮头插字符串导致性能下降。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public String addBinary(String a, String b) {
int i = a.length() - 1;
int j = b.length() - 1;
int carry = 0;
StringBuilder sb = new StringBuilder();
while (i >= 0 || j >= 0 || carry != 0) {
int sum = carry;
if (i >= 0) sum += a.charAt(i--) - '0';
if (j >= 0) sum += b.charAt(j--) - '0';
sb.append(sum % 2);
carry = sum / 2;
}
return sb.reverse().toString();
}
}func addBinary(a string, b string) string {
i, j := len(a)-1, len(b)-1
carry := 0
out := make([]byte, 0, max(len(a), len(b))+1)
for i >= 0 || j >= 0 || carry != 0 {
sum := carry
if i >= 0 {
sum += int(a[i] - '0')
i--
}
if j >= 0 {
sum += int(b[j] - '0')
j--
}
out = append(out, byte('0'+sum%2))
carry = sum / 2
}
for l, r := 0, len(out)-1; l < r; l, r = l+1, r-1 {
out[l], out[r] = out[r], out[l]
}
return string(out)
}
func max(x, y int) int {
if x > y {
return x
}
return y
}class Solution {
public:
string addBinary(string a, string b) {
int i = (int)a.size() - 1;
int j = (int)b.size() - 1;
int carry = 0;
string out;
while (i >= 0 || j >= 0 || carry) {
int sum = carry;
if (i >= 0) sum += a[i--] - '0';
if (j >= 0) sum += b[j--] - '0';
out.push_back(char('0' + (sum % 2)));
carry = sum / 2;
}
reverse(out.begin(), out.end());
return out;
}
};class Solution:
def addBinary(self, a: str, b: str) -> str:
i, j = len(a) - 1, len(b) - 1
carry = 0
out = []
while i >= 0 or j >= 0 or carry:
total = carry
if i >= 0:
total += ord(a[i]) - ord('0')
i -= 1
if j >= 0:
total += ord(b[j]) - ord('0')
j -= 1
out.append(str(total % 2))
carry = total // 2
return ''.join(reversed(out))/**
* @param {string} a
* @param {string} b
* @return {string}
*/
var addBinary = function(a, b) {
let i = a.length - 1;
let j = b.length - 1;
let carry = 0;
const out = [];
while (i >= 0 || j >= 0 || carry) {
let sum = carry;
if (i >= 0) sum += a.charCodeAt(i--) - 48;
if (j >= 0) sum += b.charCodeAt(j--) - 48;
out.push(String(sum % 2));
carry = Math.floor(sum / 2);
}
return out.reverse().join('');
};
Comments