本文共 2253 字，大约阅读时间需要 7 分钟。

题目：（中等）

标签：字符串、贪心算法、回溯算法

解法一（暴力解法）：

class Solution:    def splitIntoFibonacci(self, S: str) -> List[int]:        N = len(S)        # 判断数字是否合法        def is_valid(n):            return not (int(n) > 0 and n[0] == "0") and int(n) <= (2 ** 31 - 1)        # 检查是否为斐波那契数列        def is_fibonacci(m, n):            if not is_valid(S[:m]) or not is_valid(S[m:n]):                return False            lst = [int(S[:m]), int(S[m:n])]            idx1 = n            while idx1 < N:                nn = lst[-1] + lst[-2]  # 当前项                s1 = str(nn)                idx2 = idx1 + len(s1)                s2 = S[idx1:idx2]                if is_valid(s2) and s1 == s2:                    lst.append(nn)                    idx1 = idx2                else:                    return False            return lst        # 筛选所有的斐波那契数列        for i in range(1, N):            for j in range(i + 1, N):                fibonacci_lst = is_fibonacci(i, j)                if fibonacci_lst:                    return fibonacci_lst        return []

解法二（优化解法一）：

class Solution:    def splitIntoFibonacci(self, S: str) -> List[int]:        MAX_INT = 2147483647        N = len(S)        # 判断数字是否合法        def is_valid(n):            return not (int(n) > 0 and n[0] == "0") and int(n) <= MAX_INT        # 检查是否为斐波那契数列        def is_fibonacci(m, n):            if not is_valid(S[:m]) or not is_valid(S[m:n]):                return False            lst = [int(S[:m]), int(S[m:n])]            idx1 = n            while idx1 < N:                nn = lst[-1] + lst[-2]  # 当前项                s1 = str(nn)                idx2 = idx1 + len(s1)                s2 = S[idx1:idx2]                if is_valid(s2) and s1 == s2:                    lst.append(nn)                    idx1 = idx2                else:                    return False            return lst        # 筛选所有的斐波那契数列        for i in range(1, min(10, N)):            for j in range(i + 1, min(i + 10, N)):                fibonacci_lst = is_fibonacci(i, j)                if fibonacci_lst:                    return fibonacci_lst        return []

转载地址：https://dataartist.blog.csdn.net/article/details/108079585 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！