Problem statement

https://leetcode.com/problems/split-array-into-fibonacci-sequence/

Solution

Let n be length of original string and m = 9 is maximal length of number. Then we can check all O(m^2) possible starts and we can check this candidate in O(n). See also very similar problem 0306 Additive Number.

Complexity

Total time complexity O(nm^2) and space O(1).

Code

class Solution:
    def splitIntoFibonacci(self, S):
        n, N, m = len(S), 2**31 - 1, 9
        for i in range(1, m):
            for j in range(1, m):
                if i + j >= n: continue
                part1, part2 = S[:i], S[i:i+j]
                if part1[0] == "0" and part1 != "0": continue
                if part2[0] == "0" and part2 != "0": continue
                
                ans = [int(part1), int(part2)]
                k = i + j
                while k < n:
                    nxt = ans[-2] + ans[-1]
                    if nxt <= N and S[k:].startswith(str(nxt)):
                        k += len(str(nxt))
                        ans += [nxt]
                    else:
                        break
                        
                if k == n and len(ans) >= 3: return ans
                
        return []