LeetCode 842 - Split Array into Fibonacci Sequence

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

Given a string S of digits, such as S = "123456579", we can split it into a Fibonacci-like sequence [123, 456, 579].

Formally, a Fibonacci-like sequence is a list F of non-negative integers such that:

• 0 <= F[i] <= 2^31 - 1, (that is, each integer fits a 32-bit signed integer type);
• F.length >= 3;
• and F[i] + F[i+1] = F[i+2] for all 0 <= i < F.length - 2.

Also, note that when splitting the string into pieces, each piece must not have extra leading zeroes, except if the piece is the number 0 itself.

Return any Fibonacci-like sequence split from S, or return [] if it cannot be done.

Example 1:

Input: "123456579"
Output: [123,456,579]

Example 2:

Input: "11235813"
Output: [1,1,2,3,5,8,13]

https://leetcode.com/problems/split-array-into-fibonacci-sequence/discuss/133936/short-and-fast-backtracking-solution

public List<Integer> splitIntoFibonacci(String S) {
    List<Integer> ans = new ArrayList<>();
    helper(S, ans, 0);
    return ans;
}

public boolean helper(String s, List<Integer> ans, int idx) {
    if (idx == s.length() && ans.size() >= 3) {
        return true;
    }
    for (int i=idx; i<s.length(); i++) {
        if (s.charAt(idx) == '0' && i > idx) {
            break;
        }
        long num = Long.parseLong(s.substring(idx, i+1));
        if (num > Integer.MAX_VALUE) {
            break;
        }
        int size = ans.size();
        // early termination
        if (size >= 2 && num > ans.get(size-1)+ans.get(size-2)) {
            break;
        }
        if (size <= 1 || num == ans.get(size-1)+ans.get(size-2)) {
            ans.add((int)num);
            // branch pruning. if one branch has found fib seq, return true to upper call
            if (helper(s, ans, i+1)) {
                return true;
            }
            ans.remove(ans.size()-1);
        }
    }
    return false;
}

long num = Long.parseLong(s.substring(idx, i+1));
This could be changed to the code below for saving the memory for the substring

    public boolean helper(List<Integer> res, String S, int start) {
        if (start == S.length() && res.size() >= 3)
            return true;
        long num = 0;
        for (int i = start; i < S.length(); i++) {
            if (S.charAt(start) == '0' && i > start)
                break;
            num = num * 10 + (S.charAt(i) - '0');
            if (num > Integer.MAX_VALUE)
                break;
            if (res.size() >= 2 && res.get(res.size() - 1) + res.get(res.size() - 2) < num)
                break;
            if (res.size() <= 1 || res.get(res.size() - 1) + res.get(res.size() - 2) == num) {
                res.add((int) num);
                if (helper(res, S, i + 1))
                    return true;
                res.remove(res.size() - 1);
            }
        }
        return false;

X. Iterative

The first two elements of the array uniquely determine the rest of the sequence.

Algorithm

For each of the first two elements, assuming they have no leading zero, let's iterate through the rest of the string. At each stage, we expect a number less than or equal to 2^31 - 1 that starts with the sum of the two previous numbers.

Time Complexity: $O(N^2)$, where $N$ is the length of S, and with the requirement that the values of the answer are $O(1)$ in length.

  public List<Integer> splitIntoFibonacci(final String S) {

    int N = S.length();

    for (int i = 0; i < Math.min(10, N); ++i) {

      if (S.charAt(0) == '0' && i > 0)

        break;

      long a = Long.valueOf(S.substring(0, i + 1));

      if (a >= Integer.MAX_VALUE)

        break;

      search: for (int j = i + 1; j < Math.min(i + 10, N); ++j) {

        if (S.charAt(i + 1) == '0' && j > i + 1)

          break;

        long b = Long.valueOf(S.substring(i + 1, j + 1));

        if (b >= Integer.MAX_VALUE)

          break;

        List<Integer> fib = new ArrayList();

        fib.add((int) a);

        fib.add((int) b);

        int k = j + 1;

        while (k < N) {

          long nxt = fib.get(fib.size() - 2) + fib.get(fib.size() - 1);

          String nxtS = String.valueOf(nxt);

          if (nxt <= Integer.MAX_VALUE && S.substring(k).startsWith(nxtS)) {

            k += nxtS.length();

            fib.add((int) nxt);

          } else

            continue search;

        }

        if (fib.size() >= 3)

          return fib;

      }

    }

    return new ArrayList<Integer>();

  }

https://leetcode.com/problems/split-array-into-fibonacci-sequence/discuss/193833/Short-iterative-solution

const INT_MAX = Math.pow(2, 31) - 1;
function splitIntoFibonacci(S) {
  for (let t1 = 1; t1 < S.length; t1++) {
    for (let t2 = t1+1; t2 < S.length; t2++) {
      if (S[0] === '0' && t1 > 1) continue;
      if (S[t1] === '0' && t2 > t1+1) continue;
      
      const res = [parseInt(S.slice(0, t1)), parseInt(S.slice(t1, t2))];
      
      for (let tt = t2; tt < S.length;) {
        const sum = res[res.length-1] + res[res.length-2];
        
        if (sum > INT_MAX || !S.slice(tt).startsWith(''+sum)) break;
        
        res.push(sum);
        tt += (''+sum).length;
        if (tt === S.length) return res;
      }
    }
  }
  return [];
}

X.  http://www.cnblogs.com/grandyang/p/10434771.html
讨论：这道题只让我们返回了一个斐波那契数列，一个很好的follow up就是返回所有满足题意的序列，就像例子5一样，把两种符合题意的组合都返回出来。其实改起来相当的容易，只需要将结果res换成一个二维数组来保存所有的情况，然后在递归函数中，首先判断如果已经遍历到了S的末尾，并且out数组中的个数大于等于3了，那么将out数组加入结果res即可，其余部分和上面的解法并没有啥区别

    vector<vector<int>> splitIntoFibonacci(string S) {

        vector<vector<int>> res;

        vector<int> out;

        helper(S, 0, out, res);

        return res;

    }

    void helper(string& S, int start, vector<int>& out, vector<vector<int>>& res) {

        if (start >= S.size() && out.size() >= 3) {

            res.push_back(out); return;

        }

        for (int i = start; i < S.size(); ++i) {

            string cur = S.substr(start, i - start + 1);

            if ((cur.size() > 1 && cur[0] == '0') || cur.size() > 10) break;

            long num = stol(cur), len = out.size();

            if (num > INT_MAX) break;

            if (out.size() >= 2 && num != (long)out[len - 1] + (long)out[len - 2]) continue;

            out.push_back(num);

            helper(S, i + 1, out, res);

            out.pop_back();

        }

    }