842. Split Array into Fibonacci Sequence

Version #1 Brute Force

We can see that a Fibonacci can be uniquely defined by its 1st and 2nd number
We enumerate all the scenarios of combination of 1st and 2nd numbers check if it is valid combination

93.81 %
class Solution {
    public List<Integer> splitIntoFibonacci(String S) {
List<Integer> result = new ArrayList<>();
if (S == null || S.length() == 0) {
return result;
}
for (int i = 1; i < S.length() - 1; i++) {
// [0, i)
long first = Long.valueOf(S.substring(0, i));
if (S.charAt(0) == '0' && i != 1 || first > Integer.MAX_VALUE) {
break;
}
for (int j = i + 1; j < S.length(); j++) { // at least 3 numbers
long second = Long.valueOf(S.substring(i, j)); // [i, j)
if (S.charAt(i) == '0' && j != i + 1 || second > Integer.MAX_VALUE) {
break;
}
if (isValid(first, second, S, j)) {
result.add((int) first);
result.add((int)second);
int length = j;
long next = 0;
while (length < S.length()) {
next = first + second;
result.add((int)(next));
first = second;
second = next;
length += String.valueOf(next).length();
}
return result;
}
}
}
return result;
}

private boolean isValid(long prev, long curr, String s, int index) {
String nextStr = null;
// System.out.println("prev->" + prev + " curr->" + curr);
while (index < s.length()) {
long next = prev + curr;
if (next > Integer.MAX_VALUE) {
return false;
}

nextStr = String.valueOf(next);
for (int i = 0; i < nextStr.length(); i++) {
if (index + i >= s.length() || s.charAt(index + i) != nextStr.charAt(i)) {
return false;
}
}
index += nextStr.length();
prev = curr;
curr = next;
}
return true;
}
}