C++程序将两个二进制字符串相加

给定两个二进制字符串，返回它们的和（也是一个二进制字符串）。

例子：

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

思路是从两个字符串的最后一个字符开始，逐一计算数字总和。如果和大于1，则为下一个数字存储进位。

// C++ program to add two 
// binary strings
#include <bits/stdc++.h>
using namespace std;
  
// This function adds two binary strings 
// and return result as a third string
string addBinary(string A, string B)
{
    // If the length of string A is greater 
    // than the length of B then just swap 
    // the string by calling the same 
    // function and make sure to return 
    // the function otherwise recursion 
    // will occur which leads to calling 
    // the same function twice
    if (A.length() > B.length())
        return addBinary(B, A);
  
    // 计算两个字符串长度之间的差。
    int diff = B.length() - A.length();
  
    // 初始化填充字符串，它用于存储应添加为前缀的零，以使其长度小于另一个字符串。
    string padding;
    for (int i = 0; i < diff; i++)
        padding.push_back('0');
  
    A = padding + A;
    string res;
    char carry = '0';
  
    for (int i = A.length() - 1; i >= 0; i--) 
    {
        // 此 if 条件解决了 110 111 可能的情况。
        if (A[i] == '1' && B[i] == '1') 
        {
            if (carry == '1')
                res.push_back('1'), carry = '1';
            else
                res.push_back('0'), carry = '1';
        }
  
        // 此 if 条件解决了 000 001 可能的情况。
        else if (A[i] == '0' && B[i] == '0') 
        {
            if (carry == '1')
                res.push_back('1'), carry = '0';
            else
                res.push_back('0'), carry = '0';
        }
  
        // 此 if 条件解决了 100 101 010 011 可能的情况。
        else if (A[i] != B[i]) 
        {
            if (carry == '1')
                res.push_back('0'), carry = '1';
            else
                res.push_back('1'), carry = '0';
        }
    }
  
    // 如果在最后有进位，就将其添加到结果中。
    if (carry == '1')
        res.push_back(carry);
    // 反转结果
    reverse(res.begin(), res.end());
  
    // 去除前导零
    int index = 0;
    while (index + 1 < res.length() && 
           res[index] == '0')
        index++;
    return (res.substr(index));
}
  
// 驱动程序
int main()
{
    string a = "1101", b = "100";
    cout << addBinary(a, b) << endl;
    return 0;
}

输出：

时间复杂度 ：O(max(L1，L2))，其中L1和L2分别为字符串a和b的长度。

辅助空间 ：O(max(L1，L2))，其中L1和L2分别为字符串a和b的长度。