[leetcode] 306. Additive Number 解题报告

题目链接:https://leetcode.com/problems/additive-number/

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should containat leastthree numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

For example:
"112358"is an additive number because the digits can form an additive sequence:1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

"199100199"is also an additive number, the additive sequence is:1, 99, 100, 199.

1 + 99 = 100, 99 + 100 = 199

Note:Numbers in the additive sequencecannothave leading zeros, so sequence1, 2, 03or1, 02, 3is invalid.

Given a string containing only digits'0'-'9', write a function to determine if it's an additive number.

Follow up:
How would you handle overflow for very large input integers?

思路: 一个基本的思想就是确定了第一个和第二个数之后, 以后的数就是验证了, 所以只要枚举第一和第二个数, 然后不断验证下面的字符串子串是否是前两个数的和即可. 因为数字可能超出整数的范围, 因此在验证一个数是否是另外两个和的时候, 可以用字符串相加来模拟整数相加. 另外需要注意的是'0'字符, 如果他在子串的首位, 那么他只能以"0"的形式存在, 并且"0"只可能作为第一个数或者第二个数.

代码如下:

class Solution {
public:
    string add(string s1, string s2)
    {
        string result;
        int flag = 0, i = s1.size()-1, j = s2.size()-1;
        while(i >=0 || j >=0)
        {
            int num1=0, num2=0;
            if(i >=0) num1 = s1[i]-'0';
            if(j >= 0) num2 = s2[j]-'0';
            result.insert(result.begin(), '0'+(num1+num2+flag)%10);
            flag = (num1+num2+flag)/10;
            i--, j--;
        }
        if(flag == 1) result.insert(result.begin(), '1');
        return result;
    }
    
    bool DFS(string num, string num1, string num2)
    {
        if(num.size()==0 || num[0] == '0') return false;
        for(int i =0; i