842. Split Array into Fibonacci Sequence

Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579].

Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:

0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
F.length >= 3;
and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2.
Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.

Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.

Example 1:

Input: "123456579"
Output: [123,456,579]
Example 2:

Input: "11235813"
Output: [1,1,2,3,5,8,13]
Example 3:

Input: "112358130"
Output: []
Explanation: The task is impossible.
Example 4:

Input: "0123"
Output: []
Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.
Example 5:

Input: "1101111"
Output: [110, 1, 111]
Explanation: The output [11, 0, 11, 11] would also be accepted.
Note:

1 <= S.length <= 200
S contains only digits.

这题和Additive Number一样的，但是需要注意的是溢出后就可以不继续计算下去了。

class SplitArrayIntoFibonacciSequence : 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;
    }
    vector<int> splitIntoFibonacci(string S) {
        if (S.size() <= 2) return vector<int>();
        vector<int> res;

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