[842][中等][DFS] 将数组拆分成斐波那契序列

题目描述

842. 将数组拆分成斐波那契序列

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

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

• 0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；

• F.length >= 3；

• 对于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2] 成立。

另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。

返回从 S 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。

解题思路

遍历整个字符串, 使用DFS的思路, 逐段截取, 判断是否符合斐波那契序列的条件, 满足则添加到当前序列中, 继续向下遍历; 否则向上回溯.

注意:

• 如果当前序列长度小于3, 则遇到数直接添加到序列中, 然后才判断斐波那契序列的条件

• 停止条件是索引越界, 这时说明最后一个字符和组成数字, 被添加到序列中了. 如果此时的序列长度不小于3, 就得到了一个斐波那契式的序列, 返回

本题最重要的是进行剪枝优化, 具体剪枝点见代码.

class Solution:
    UPPER = 2 ** 31 - 1

    def splitIntoFibonacci(self, S: str) -> List[int]:
        n = len(S)
        result = []

        def dfs(start, series):
            if start == n:
                if len(series) >= 3:
                    result.append(series)
                    return True  # 找到一个就可以返回, 不必再继续寻找, 应做剪枝
                return

            for i in range(start, n):
                sub = S[start: i + 1]
                if not (sub.startswith('0') and len(sub) > 1):  # 剪枝1, 每个数字块不能以0开头, 单独的0除外
                    number = int(sub)
                    if number > self.UPPER:  # 剪枝2, 如果当前数值过大, 后续的会更大, 不再继续向后搜索
                        break

                    if len(series) >= 2:
                        if number == series[-1] + series[-2]:
                            if dfs(i + 1, series + [number]):  # 剪枝4, 已经找到一个结果, 无需继续查找
                                return True
                        elif number > series[-1] + series[-2]:  # 剪枝3, 当前的数字已经大过期待值, 后续更大, 不再向后搜索
                            break
                    else:  # 还没有凑齐两个数字, 先填至两个数字
                        if dfs(i + 1, series + [number]):  # 剪枝4, 已经找到一个结果, 无需继续查找
                            return True

        dfs(0, [])
        return result[0] if len(result) > 0 else result