力扣–累加数

一、问题描述

二、分析

• 这道题第一眼看可能觉得比较简单，枚举前后3个位置，判断这3个位置的数字是否满足题目的要求（第三个数 = 前两个数之和）
• 但是看到后面的用例就会发现问题：199100199==》这3个数不一定是1位数，可能是多位数，所以都需要进行枚举

• 定义i,j,k分别代表第一个数字、第二个数字和第三个数字的起始下标，这样好处在于计算各个字符串时都很方便。
• 第一个数字的起始下标一定是0，但是第二和第三个数字的起始下标不固定，需要通过两层循环枚举，在拿到起始数字之后，就可以dfs一直到最后验证是否整个字符串符合要求。
• 这道题dfs的递归结束条件和普通稍有不同。这里递归成功的标志是一直到字符串最后一个字符都满足要求，即是累加序列，那么我们需要看是否能够递归到最后一个位置正好结束。
• 为了处理大正数相加应该使用两字符串相加的程序，并且与和的字符串比较，避免转换为int消耗时间与溢出。

三、代码

class Solution {
public:
	//字符串相加函数
    string add(string& a,string& b)
    {
        int n1 = a.size() - 1;
        int n2 = b.size() - 1;
        int carry = 0;
        string ans;
        while(n1 >= 0 || n2 >= 0 || carry > 0)
        {
            int t1 = n1 >= 0 ? a[n1--] - '0' : 0;
            int t2 = n2 >= 0 ? b[n2--] - '0' : 0;
            ans += (t1 + t2 + carry) % 10 + '0';
            carry = (t1 + t2 + carry) >= 10 ? 1 : 0;
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }

    bool dfs(string& str,int i,int j,int k)
    {
    	//代表第一个数字的下标以0开始并且不等于0
    	//代表第二个数字的下标以0开始并且不等于0
    	//代表第三个数字的下标以0开始并且不等于0
    	//这三种情况都是false的
        if((str[i] == '0' && i + 1 < j) || (str[j] == '0' && j + 1 < k) || (str[k] == '0' && k + 1 < str.size() - 1))
        {
            return false;
        }

		//取出前两个数字
        string num1 = str.substr(i,j - i);
        string num2 = str.substr(j,k - j);

		//计算前脸个数字的和，避免大数溢出采用字符串相加的方式
        string add_num = add(num1,num2);

        int n = add_num.size();
        //代表如果第三个数字的起始位置k到字符结束的位置字符的数量小于n
        //就代表一定不满足条件(长度都不够肯定不想等)
        if(n > str.size() - k)
        {
            return false;
        }
        
        //获取第三个数字
        string num3 = str.substr(k,n);

		//现在长度相等但是值不相等直接返回false
        if(num3 != add_num)
        {
            return false;
        }

		//按照题目要求，只有整个str都满足时才算叠加序列
		//即第三个数字刚好是k到str的末尾
        if(k + n == str.size())
        {
            return true;
        }

		//反之代表当前没走到str的末尾，继续递归
        return dfs(str,j,k,k + n);
    }

    bool isAdditiveNumber(string num) {
    	//直接排除特殊情况
        if(num.size() < 3)
        {
            return false;
        }

		//i代表第一个数字的起始下标
		//j代表第二个数字的起始下标
		//k代表第三个数字的起始下标
		//第一个数字一定是从0位置开始的
        int i = 0;

		//枚举第二个数字的起始下标j
        for(int j = i + 1;j < num.size();j++)
        {
        	//枚举第三个数字的起始下标k
            for(int k = j + 1;k < num.size();k++)
            {
                if(dfs(num,i,j,k))
                {
                    return true;
                }
            }
        }
        return false;
    }
};