C++刷leetcode（67. 二进制求和）【递归】

糖逗

题目描述：

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

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

 

示例 1:

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

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-binary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    void dfs(string & a, string & b, string& res, int cura, int curb, int store){
        if(cura < 0 && curb < 0){
            if(store != 0) res += '1';
            return;
        }
        if(cura < 0){
            int temp = b[curb] - '0' + store;
            if(temp >= 2){
                store = 1;
                if(temp == 2)res += '0';
                else res += '1';
            }
            else if(temp < 2){
                char temp2 = temp + '0';
                res += temp2;
                store = 0; 
            }
            dfs(a, b, res, -1, curb - 1, store);
        }
        else if(curb < 0){
            int temp = a[cura] - '0' + store;
            if(temp >= 2){
                store = 1;
                if(temp == 2)res += '0';
                else res += '1';
            }
            else if(temp < 2){
                char temp2 = temp + '0';
                res += temp2;
                store = 0; 
            }

            dfs(a, b, res, cura-1, -1, store);
        }
        else{
            int temp = a[cura] - '0' + b[curb] - '0' + store;
            if (temp >= 2){
                store = 1;
                if(temp == 2)res += '0';
                else res += '1';
            }else if(temp < 2){
                char temp2 = temp + '0';
                res += temp2;
                store = 0;
            }
            dfs(a, b, res, cura-1, curb-1, store);
        }
    }
    string addBinary(string a, string b) {
        string res;
        dfs(a, b, res, a.size()-1, b.size() - 1, 0);
        reverse(res.begin(), res.end());
        return res;
    }
};