Medium

题目描述

给定一个数字字符串 num，比如 "123456579"。我们可以将它拆分成斐波那契数列 [123, 456, 579]。

形式上，斐波那契数列是一个非负整数列表 f，满足：

  • 0 <= f[i] < 2^31（即每个整数都在32位有符号整数类型范围内）
  • f.length >= 3
  • 对于所有 0 <= i < f.length - 2，都有 f[i] + f[i + 1] == f[i + 2]

注意，当将字符串拆分成片段时，每个片段都不能有多余的前导零，除非该片段是数字 0 本身。

返回从 num 拆分出的任意斐波那契数列，如果无法拆分则返回 []。

示例 1:

输入: num = "1101111"
输出: [11,0,11,11]
解释: 输出 [110, 1, 111] 也是可以接受的。

示例 2:

输入: num = "112358130"
输出: []
解释: 无法拆分。

示例 3:

输入: num = "0123"
输出: []
解释: 不允许前导零，所以 "01", "2", "3" 是无效的。

约束条件:

  • 1 <= num.length <= 200
  • num 仅包含数字

解题思路

这是一道典型的回溯问题。我们需要尝试所有可能的拆分方式来构造斐波那契序列。

解题思路：

  1. 回溯搜索：我们首先确定前两个数字，然后根据斐波那契性质推导后续数字

  2. 边界条件处理：

    • 每个数字不能有前导零（除非数字本身是0）
    • 每个数字必须在32位整数范围内
    • 序列长度至少为3

  3. 优化策略：

    • 前两个数字的长度有上限：如果第一个数长度为i，第二个数长度为j，那么i+j不能超过字符串长度的一半（因为后续数字会越来越长）
    • 一旦确定前两个数字，后续的拆分就是确定性的

  4. 具体实现：

    • 外层双重循环枚举前两个数字的所有可能长度
    • 对于每种组合，使用回溯验证是否能构成完整的斐波那契序列
    • 在回溯过程中，每次计算下一个应该出现的数字，然后检查字符串中对应位置是否匹配

推荐解法：回溯 + 剪枝，时间复杂度相对较优，代码清晰易懂。

代码实现

class Solution {
public:
    vector<int> splitIntoFibonacci(string num) {
        vector<int> result;
        backtrack(num, 0, result);
        return result;
    }
    
private:
    bool backtrack(const string& num, int index, vector<int>& path) {
        if (index == num.length()) {
            return path.size() >= 3;
        }
        
        long long current = 0;
        for (int i = index; i < num.length(); i++) {
            // 避免前导零
            if (i > index && num[index] == '0') break;
            
            current = current * 10 + (num[i] - '0');
            
            // 超出32位整数范围
            if (current > INT_MAX) break;
            
            if (path.size() < 2 || 
                (long long)path[path.size()-1] + path[path.size()-2] == current) {
                path.push_back((int)current);
                if (backtrack(num, i + 1, path)) {
                    return true;
                }
                path.pop_back();
            } else if (path.size() >= 2 && 
                      (long long)path[path.size()-1] + path[path.size()-2] < current) {
                break;  // 当前数已经太大，后续不可能匹配
            }
        }
        return false;
    }
};

class Solution:
    def splitIntoFibonacci(self, num: str) -> List[int]:
        def backtrack(index, path):
            if index == len(num):
                return len(path) >= 3
            
            current = 0
            for i in range(index, len(num)):
                # 避免前导零
                if i > index and num[index] == '0':
                    break
                
                current = current * 10 + int(num[i])
                
                # 超出32位整数范围
                if current > 2**31 - 1:
                    break
                
                if len(path) < 2 or path[-1] + path[-2] == current:
                    path.append(current)
                    if backtrack(i + 1, path):
                        return True
                    path.pop()
                elif len(path) >= 2 and path[-1] + path[-2] < current:
                    break  # 当前数已经太大，后续不可能匹配
            
            return False
        
        result = []
        backtrack(0, result)
        return result

public class Solution {
    public IList<int> SplitIntoFibonacci(string num) {
        var result = new List<int>();
        if (Backtrack(num, 0, result)) {
            return result;
        }
        return new List<int>();
    }
    
    private bool Backtrack(string num, int index, List<int> path) {
        if (index == num.Length) {
            return path.Count >= 3;
        }
        
        long current = 0;
        for (int i = index; i < num.Length; i++) {
            // 避免前导零
            if (i > index && num[index] == '0') break;
            
            current = current * 10 + (num[i] - '0');
            
            // 超出32位整数范围
            if (current > int.MaxValue) break;
            
            if (path.Count < 2 || 
                (long)path[path.Count-1] + path[path.Count-2] == current) {
                path.Add((int)current);
                if (Backtrack(num, i + 1, path)) {
                    return true;
                }
                path.RemoveAt(path.Count - 1);
            } else if (path.Count >= 2 && 
                      (long)path[path.Count-1] + path[path.Count-2] < current) {
                break;  // 当前数已经太大，后续不可能匹配
            }
        }
        return false;
    }
}

var splitIntoFibonacci = function(num) {
    const result = [];
    
    function backtrack(index, sequence) {
        if (index === num.length) {
            return sequence.length >= 3;
        }
        
        for (let i = index; i < num.length; i++) {
            const substr = num.slice(index, i + 1);
            
            if (substr.length > 1 && substr[0] === '0') {
                break;
            }
            
            const numVal = parseInt(substr);
            if (numVal > Math.pow(2, 31) - 1) {
                break;
            }
            
            if (sequence.length < 2) {
                sequence.push(numVal);
                if (backtrack(i + 1, sequence)) {
                    return true;
                }
                sequence.pop();
            } else {
                const expectedSum = sequence[sequence.length - 1] + sequence[sequence.length - 2];
                if (numVal === expectedSum) {
                    sequence.push(numVal);
                    if (backtrack(i + 1, sequence)) {
                        return true;
                    }
                    sequence.pop();
                } else if (numVal > expectedSum) {
                    break;
                }
            }
        }
        
        return false;
    }
    
    if (backtrack(0, result)) {
        return result;
    }
    
    return [];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n²)
空间复杂度O(n)

说明：

  • 时间复杂度：在最坏情况下，我们需要尝试所有可能的前两个数字的组合，这大约是O(n²)种可能。对于每种组合，验证过程是O(n)
  • 空间复杂度：主要是递归调用栈和结果数组的空间，最深递归深度为O(n)

相关题目