leetcode842. Split the array into Fibonacci sequences

subject

Given a string of numbers S, such as S = "123456579", We can divide it into Fibonacci sequences [123, 456, 579].

Formally , The Fibonacci sequence is a list of nonnegative integers F, And meet ：

• 0 <= F[i] <= 2^31 - 1,（ in other words , Every integer matches 32 Bit signed integer type ）;
• F.length >= 3;
• For all 0 <= i < F.length - 2, There are F[i] + F[i+1] = F[i+2] establish .

in addition , Please note that , When you split a string into small pieces , The number of each block must not start with zero , Unless this block is a number 0 In itself .

Return from S Any set of Fibonacci sequence blocks that are split out , If it can't be split, return [].

 

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 : []
 explain :  The task cannot be accomplished .

Example 4：

 Input ："0123"
 Output ：[]
 explain ： The number of each block cannot start with zero , therefore  "01","2","3"  Not a valid answer .

Example 5：

 Input : "1101111"
 Output : [110, 1, 111]
 explain :  Output  [11,0,11,11]  It's also accepted .

Tips ：

1. 1 <= S.length <= 200
2. character string S There are only numbers in it .

public static List<Integer> _143_fabonaci(String text) {
        List<Integer> result = new ArrayList<>();
        boolean suc = dfsFabonaci(text.toCharArray(), 0, result);
        // If you return true, explain  result  The array satisfies the Fibonacci sequence 
        return suc ? result : new ArrayList<>();
    }
​
    private static boolean dfsFabonaci(char[] chars, int index, List<Integer> result) {
        if (index == chars.length && result.size() >= 3) {
            return true;
        }
        if (index == chars.length) {
            return false;
        }
​
        Long num = 0L;
        int cursor = index;
        while (cursor < chars.length) {
            num = num * 10 + (chars[cursor] - '0');
            if (num > Integer.MAX_VALUE) {
                break;
            }
​
            // The current number exceeds the previous two , prune 
            if ((result.size() >= 2 && result.get(result.size() - 1) + result.get(result.size() - 2) < num.intValue())) {
                break;
            }
​
            // The current list is less than two , Or the first two sums of the current list are equal to the current value , Recursion 
            if ((result.size() < 2 || result.get(result.size() - 1) + result.get(result.size() - 2) == num.intValue())) {
                result.add(num.intValue());
                boolean res = dfsFabonaci(chars, cursor + 1, result);
                if (res) {
                    return true;
                }
                result.remove(result.size() - 1);
            }
​
            // If you encounter 0, There is no need to continue , prevent  0xx  Numbers 
            if (num == 0L) {
                break;
            }
            cursor++;
        }
​
        return false;
    }