LeetCode 306. 累加数--DFS模拟

306. 累加数
     累加数是一个字符串，组成它的数字可以形成累加序列。

一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。

给定一个只包含数字 ‘0’-‘9’ 的字符串，编写一个算法来判断给定输入是否是累加数。

说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。

示例 1:

输入: “112358”
输出: true
解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
示例 2:

输入: “199100199”
输出: true
解释: 累加序列为: 1, 99, 100, 199。1 + 99 = 100, 99 + 100 = 199
进阶:
你如何处理一个溢出的过大的整数输入?

题解

直接DFS模拟，长度比较短，保证不会超时，因为涉及大数运算，直接用python实现，而且python字符串转数字也比较方便，注意前缀0的特判。

AC代码

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        def fun(pos,num,a,b,n):
            if pos==n:
                return True
            for i in range(pos,n):
                c=num[pos:i+1]
                if c[0]=='0' and len(c)>1:
                    continue
                c=int(c)
                if a+b==c:
                    res=fun(i+1,num,b,c,n)
                    if res==True:
                        return True
            return False        
        n=len(num)
        for i in range(n-1):
            for j in range(i+1,n-1):
                a=num[0:i+1]
                if a[0]=='0' and len(a)>1:
                    continue
                b=num[i+1:j+1]
                if b[0]=='0' and len(b)>1:
                    continue
                a=int(a)
                b=int(b)
                res=fun(j+1,num,a,b,n)
                if res==True:
                    return True
        return False