842. Split Array into Fibonacci Sequence

Medium (Trung bình) C++ Python 🔗 Xem trên LeetCode

📋 Đề Bài

You are given a string of digits num, such as "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³¹, (that is, each integer fits in 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.

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 num, or return [] if it cannot be done.

Example 1:

Input: num = "1101111"
Output: [11,0,11,11]
Explanation: The output [110, 1, 111] would also be accepted.

Example 2:

Input: num = "112358130"
Output: []
Explanation: The task is impossible.

Example 3:

Input: num = "0123"
Output: []
Explanation: Leading zeroes are not allowed, so "01", "2", "3" is not valid.

Constraints:

1 <= num.length <= 200
num contains only digits.

🧠 Thuật Toán & Kỹ Thuật

DFS (Tìm kiếm theo chiều sâu)Bit Manipulation (Thao tác bit)String (Chuỗi)

⏱️ Thời gian O(V+E)

💾 Không gian O(V)

💻 Lời Giải

C++ 0842-split-array-into-fibonacci-sequence.cpp

using ll = long long;
const ll LIMIT = 1 << 31;

class Solution {
private:
    vector<int> path;
    int n;
    
public:
    bool dfs(string &num, int i, ll f1, ll f2, int size) {
        if (i == n) {
            return size > 2;
        }
        ll totalDEC = 0;
        for (int j = i; j < n; ++j) {
            totalDEC = 10*totalDEC + (num[j] - '0') * 1LL;
            if (num[i] == '0' and j > i) {
                break;
            }
            if ((ll)INT_MAX < totalDEC) {
                break;
            }
            if (size < 2 or f1 + f2 == totalDEC) {
                path.push_back(totalDEC);
                if (dfs(num, j + 1, f2, totalDEC, size + 1)) {
                    return true;
                }
                path.pop_back();
            }
        }
        return false;
    }
    vector<int> splitIntoFibonacci(string num) {
        n = num.size();
        dfs(num, 0, 0LL, 0LL, 0LL);
        return path;
    }
};

Python 0842-split-array-into-fibonacci-sequence.py

class Solution:
    def splitIntoFibonacci(self, num: str) -> List[int]:
        n = len(num)
        self.path = []
        MAX_INT = 2**31
        
        def dfs(i, f1, f2, size):
            if i == n:
                return size > 2
            s = 0
            for j in range(i, n):
                if num[i] == '0' and j > i:
                    break
                s = s*10 + ord(num[j]) - ord('0')
                if s > MAX_INT:
                    break                
                if size < 2 or f1 + f2 == s:
                    self.path.append(s)
                    if dfs(j + 1, f2, s, size + 1):
                        return True
                    self.path.pop()
            
            return False
        
        dfs(0, 0, 0, 0)
            
        return self.path