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.

Bruteforce and Back Tracking Algorithm to Split String into Fibonacci Numbers

The start of the Fiboancci Numbers can be obtained via Bruteforce algorithms in O(N^2). Once we determine the first two numbers, we can start backtracking searching in the rest of of the string.

We also need to make sure the numbers in the sequence are smaller than the 32-bit signed integer (2³¹-1). Once the search reaches the end and matches the current Fiboancci number, we can simply return the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

class Solution {
public:
    vector<int> splitIntoFibonacci(string S) {
        for (int i = 0; i < S.size(); ++ i) {            
            string aa = S.substr(0, i + 1);
            if (tooBig(aa)) break;
            int a = atoi(aa.c_str());    
            if (a < 0) continue;
            for (int j = i + 1; j + aa.size() < S.size(); ++ j) {                
                vector<int> r;       
                r.push_back(a);
                string bb = S.substr(i + 1, j - i);          
                if (tooBig(bb)) break;
                if ((bb[0] == '0') && (bb.size() > 1)) break;
                int b = atoi(bb.c_str());
                r.push_back(b);
                if (check(S.substr(j + 1), a, b, r)) {
                    return r;
                }
            }
        }
        return {};
    }
    
private:
    bool tooBig(string x) {
        const string BIG = "2147483647";
        return (x.size() > BIG.size()) || ((x.size() == BIG.size()) && (x > BIG));
    }
    
    bool check(string num, int64_t prev, int64_t cur, vector<int> &r) {
        int64_t next = prev + cur;
        string x = std::to_string(next);
        if (tooBig(x)) return false;
        if (num.size() < x.size()) return false;
        if (num.substr(0, x.size()) != x) return false;
        r.push_back(next);
        if (num.size() == x.size()) {            
            return true;
        }
        return check(num.substr(x.size()), cur, next, r);
    }
};

class Solution {
public:
    vector<int> splitIntoFibonacci(string S) {
        for (int i = 0; i < S.size(); ++ i) {            
            string aa = S.substr(0, i + 1);
            if (tooBig(aa)) break;
            int a = atoi(aa.c_str());    
            if (a < 0) continue;
            for (int j = i + 1; j + aa.size() < S.size(); ++ j) {                
                vector<int> r;       
                r.push_back(a);
                string bb = S.substr(i + 1, j - i);          
                if (tooBig(bb)) break;
                if ((bb[0] == '0') && (bb.size() > 1)) break;
                int b = atoi(bb.c_str());
                r.push_back(b);
                if (check(S.substr(j + 1), a, b, r)) {
                    return r;
                }
            }
        }
        return {};
    }
    
private:
    bool tooBig(string x) {
        const string BIG = "2147483647";
        return (x.size() > BIG.size()) || ((x.size() == BIG.size()) && (x > BIG));
    }
    
    bool check(string num, int64_t prev, int64_t cur, vector<int> &r) {
        int64_t next = prev + cur;
        string x = std::to_string(next);
        if (tooBig(x)) return false;
        if (num.size() < x.size()) return false;
        if (num.substr(0, x.size()) != x) return false;
        r.push_back(next);
        if (num.size() == x.size()) {            
            return true;
        }
        return check(num.substr(x.size()), cur, next, r);
    }
};

When we do the back tracking, we can discard current search branch if the current number in the Fiboancci does not appear at the begin of the string. Instead of String.startsWith or IndexOf checks, we can use substring to get the same length of the begining of the string and compare the equality. If the string is itself the current number of Fibonacci number, we have found a good path – then we need to return true.

Also, we need to make sure the numbers does not start with ‘0’ except the number ‘0’ itself. The runtime complexity is O(N^3).

–EOF (The Ultimate Computing & Technology Blog) —