Split Array into Fibonacci Sequence
Intuition
Solution
class Solution:
def splitIntoFibonacci(self, S: str) -> List[int]:
if len(S) < 3:
return []
for i in range(1, len(S)):
for j in range(i + 1, len(S)):
x = S[:i]
y = S[i:j]
if int(x) > 2147483648 or int(y) > 2147483648:
break
tmp = [x, y]
if x[0] == '0' and x != '0':
continue
elif y[0] == '0' and y != '0':
continue
index = j
while S[index:].startswith(str(int(x) + int(y))):
x, y = y, str(int(x) + int(y))
if int(y) > 2147483648:
break
index += len(y)
tmp.append(y)
if index == len(S):
return [int(m) for m in tmp]
return []