1
MAX = 2**31
2

3

4
def consume_tail(current, s):
5
    # Following the definition of the fibonacci sequence
6
    # we know that the sum of the last two values in our
7
    # `current` list determines the next value in the sequence.
8
    # So that value, our "target", is what we're looking for next in
9
    # `s`.
10
    target = current[-1] + current[-2]
11

12
    if target > MAX:
13
        return False
14

15
    sTarget = str(target)
16
    # If the next value in the fibonacci sequence
17
    # is found at the beginning of s
18
    # we can continue to process the remaining
19
    # portion of the string.
20
    if s.find(sTarget) == 0:
21
        current.append(target)
22
    else:
23
        return False
24

25
    if sTarget != s:
26
        return consume_tail(current, s[len(sTarget) :])
27

28
    return current
29

30

31
class Solution:
32
    def splitIntoFibonacci(self, num: str) -> List[int]:
33

34
        # Identify candidate for the first
35
        # number in fibonacci sequence
36
        for i in range(len(num)):
37
            if num[0] == "0" and i > 0:
38
                break
39

40
            first = num[0 : i + 1]
41

42
            # If our current candidate for the first number
43
            # of the sequence is already larger that our
44
            # maximum value in the spec, don't bother doing anymore work.
45
            if int(first) > MAX:
46
                return []
47

48
            tail = num[i + 1 :]
49

50
            # Identify candidate for the scond
51
            # number in fibonacci sequence
52
            for j in range(len(tail)):
53
                if tail[0] == "0" and j > 0:
54
                    break
55

56
                second = tail[0 : j + 1]
57
                if int(second) > MAX:
58
                    break
59

60
                # With our current candidates (first and second),
61
                # we can consume the remaining portion of the string (tail[j+1:])
62
                # to determine if it contains the correct values for a fibonacci sequence
63
                # beginning with [first, second]
64
                result = consume_tail([int(first), int(second)], tail[j + 1 :])
65
                if result:
66
                    return result
67
        return []