306. Additive Number

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

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

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

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Example 1:

Input: "112358"
Output: true
Explanation: 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

Example 2:

Input: "199100199"
Output: true
Explanation: The additive sequence is: 1, 99, 100, 199. 
             1 + 99 = 100, 99 + 100 = 199

Constraints:

• num consists only of digits '0'-'9'.
• 1 <= num.length <= 35 Follow up: How would you handle overflow for very large input integers?

Solution

Approach 1: O(n^2).

Code (Python)

Approach 1:

Code (C++)

Approach 1:

class Solution {
private:
    int getNext(string num, int head, long target) {
        long tmp = target;
        int len = 0;
        do
        {
            len++;
            tmp /= 10;
        }
        while (tmp);
        if (head + len - 1 >= num.size())
            return -1;
        for (int i = len; i > 0; --i)
        {
            if (num[head + i - 1] - '0' != target % 10)
                return -1;
            target /= 10;
        }
        return head + len - 1;
    }
public:
    bool isAdditiveNumber(string num) {
        int n = num.size();
        if (n < 3)
            return false;
        for (int tail1 = 0; tail1 < n; ++tail1)
        {
            if (tail1 > 0 && num[0] == '0')
                continue;
            for (int tail2 = tail1+1; tail2 < n; ++tail2)
            {
                if (tail2 - tail1 > 1 && num[tail1+1] == '0')
                    continue;
                long num1 = stol(num.substr(0, tail1+1));
                long num2 = stol(num.substr(tail1+1, tail2-tail1));
                int head3 = tail2 + 1;
                while (head3 < n)
                {
                    long sum = num1 + num2;
                    int tail3 = getNext(num, head3, sum);
                    if (tail3 < 0)
                        break;
                    else if (tail3 == n - 1)
                        return true;
                    num1 = num2;
                    num2 = sum;
                    head3 = tail3 + 1;
                }
            }
        }
        return false;
    }
};