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?

这题让求一个数是否为前两个数字的和，循环往复。

只要确定了前两个数字，就能检测是否符合条件，所以直接遍历所有的可能性即可。

class AdditiveNumber : public Solution {
public:
    void Exec() {
    }
    int64_t str2int(string &num, int at, int len) {
        int64_t value = 0;
        int64_t base = 1;
        char lastChar = 0;
        for (int i = at + len - 1; i >= at; i--) {
            value += (num[i] - '0') * base;
            base *= 10;
            lastChar = num[i];
        }
        if (lastChar == '0' && len > 1) return -1;
        return value;
    }
    bool isAdditiveNumber(string num) {
        if (num.size() <= 2) return false;

        for (int flen = 1; flen <= num.size() / 2; flen++) {
            for (int slen = 1; slen <= num.size() / 2; slen++) {
                int index = flen + slen;
                int64_t fv = str2int(num, 0, flen);
                int64_t sv = str2int(num, flen, slen);
                if (fv < 0 || sv < 0) continue;
                int nexti = flen + slen;
                string want = std::to_string(fv + sv);
                while (num.size() - 1 - nexti + 1 >= want.size() &&
                       0 == memcmp(num.c_str() + nexti, want.c_str(),
                                   want.size())) {
                    nexti += want.size();
                    if (nexti >= num.size()) return true;
                    int64_t nextv = fv + sv;
                    fv = sv;
                    sv = nextv;
                    want = std::to_string(fv + sv);
                }
            }
        }
        return false;
    }
};