题目描述

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空 字符串且只包含数字 1 和 0。

样例

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

输入: a = "1010", b = "1011"
输出: "10101"

提示：

• 每个字符串仅由字符 '0' 或 '1' 组成。
• 1 <= a.length, b.length <= 10^4
• 字符串如果不是 "0" ，就都不含前导零。

算法分析

类似高精度加法的原理

• 1、对a字符串和b字符串进行反转
• 2、枚举所有位，将t = t + a[i] + b[i]对t % 2 (2取模)的值放在当前位，将t / 2 (剩下的)放在下一位
• 3、若枚举完所有位后，t > 0，将t再次存入到下一位
• 4、将ans字符串进行反转返回

时间复杂度 $O(max(n, m))$

n表示a的长度，m表示b的长度

Java 代码

class Solution {
    public String addBinary(String a, String b) {

        StringBuffer sba = new StringBuffer(a);
        StringBuffer sbb = new StringBuffer(b);
        sba = sba.reverse();
        sbb = sbb.reverse();

        StringBuffer ans = new StringBuffer("");
        int t = 0;
        for(int i = 0;i < sba.length() || i < sbb.length();i ++)
        {
            if(i < sba.length()) t += sba.charAt(i) - '0';
            if(i < sbb.length()) t += sbb.charAt(i) - '0';
            ans.append(t % 2);
            t /= 2;
        }
        if(t != 0) ans.append(t);

        return ans.reverse().toString();
    }
}