一、题目

给定两个二进制字符串，返回他们的和 (用二进制表示)。输入为非空字符串且只包含数字 1 和 0。

输入: a = "11", b = "1" 输出: "100"

---

二、解法

运算过程中，遇到某一个串不够用，需要用 0 将短的字符串补齐。从末尾开始计算，让 a、b 两个字符串逐位相加，把结果先放到 ans 列表中(从头开始放)，最后如果有进位，则在前方进行字符串拼接添加进位。最后我们只要 reserve 字符串。

public String addBinary(String a, String b) { char[] s1 = a.toCharArray(); char[] s2 = b.toCharArray(); int p1 = s1.length-1, p2 = s2.length-1; StringBuilder sb = new StringBuilder(); int ca = 0; while (p1 >=0 || p2 >= 0) { int m = p1 >= 0 && s1[p1--] == '1' ? 1 : 0; //如果sum >= 2(也就是对位都是'1'), 那么ans的相同位置变为'1'，否则变为'0' int n = p2 >= 0 && s2[p2--] == '1' ? 1 : 0; ca += m + n; sb.append(ca % 2); ca /= 2; //如果sum两次都加上了1，那么ca/2 == 1可以进位。否则ca == 0 } if (ca > 0) sb.append(ca); return sb.reverse().toString(); }

复杂度分析

时间复杂度：$O(n/m)$，空间复杂度：$O(n/m)$，

---

类似题目：

加一 简单二进制求和 简单字符串相加 简单