306. 累加数

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

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

给你一个只包含数字 ‘0’-‘9’ 的字符串，编写一个算法来判断给定输入是否是 累加数 。如果是，返回 true ；否则，返回 false 。

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

固定前两位之后，第三位就能直接推出来。

疯狂试错得到的正确解答。主要问题是解决以下几个例子：

• “1203”
• “1020305080130210”
• “1023”

诸如此类含0的处理，花了很久时间。

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        n = len(num)
        if n < 3:
            return False
        # 遍历寻找
        a0 = 0

        def findadditive(self, num, a0, a1, b1):
            if not a0 == a1 and num[a0] == '0':
                return False
            if not a1+1 == b1 and num[a1+1] == '0':
                return False
            
            a = int(num[a0:a1+1])
            b = int(num[a1+1:b1+1])
            c1_0 = max(a1-a0 +1, b1 - a1) + b1
            c1_1 = max(a1-a0 +1, b1 - a1) + b1 + 1

            flag_1 = True
            flag_2 = True
            if not b1+1 == c1_0 and num[b1+1] == '0':
                flag_1 = False
            if num[b1+1] == '0':
                flag_2 = False

            if c1_0 == n-1 and a + b == int(num[b1+1:c1_0+1]) and flag_1:
                return True
            if c1_1 == n-1 and a + b == int(num[b1+1:c1_1+1]) and flag_2:
                return True

            if c1_0 < n-1 and a + b == int(num[b1+1:c1_0+1]) and flag_1:
                if findadditive(self,num,a1+1,b1,c1_0):
                    return True
                else:
                    return False
            if c1_1 < n-1 and a + b == int(num[b1+1:c1_1+1]) and flag_2:
                if findadditive(self,num,a1+1,b1,c1_1):
                    return True
                else:
                    return False
            return False

        for a1 in range(a0,n-2):
            for b1 in range(a1+1, n-1):
                ## 确定a1 b1之后，c1的位数只有两种情况：max(a1-a0 +1, b1 - a1) 或者 max(a1-a0 +1, b1 - a1) + 1
                # print(a0,a1,b1)
                if findadditive(self, num, a0, a1, b1):
                    return True
            
        return False

官方标答：

class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        n = len(num)
        for secondStart in range(1, n-1):
            if num[0] == '0' and secondStart != 1:
                break
            for secondEnd in range(secondStart, n-1):
                if num[secondStart] == '0' and secondStart != secondEnd:
                    break
                if self.valid(secondStart, secondEnd, num):
                    return True
        return False
    
    def valid(self, secondStart: int, secondEnd: int, num: str) -> bool:
        n = len(num)
        firstStart, firstEnd = 0, secondStart - 1
        while secondEnd <= n - 1:
            third = self.stringAdd(num, firstStart, firstEnd, secondStart, secondEnd)
            thirdStart = secondEnd + 1
            thirdEnd = secondEnd + len(third)
            if thirdEnd >= n or num[thirdStart:thirdEnd+1] != third:
                break
            if thirdEnd == n-1:
                return True
            firstStart, firstEnd = secondStart, secondEnd
            secondStart, secondEnd = thirdStart, thirdEnd
        return False
    
    def stringAdd(self, s: str, firstStart: int, firstEnd: int, secondStart: int, secondEnd: int) -> str:
        third = []
        carry, cur = 0, 0
        while firstEnd >= firstStart or secondEnd >= secondStart or carry != 0:
            cur = carry
            if firstEnd >= firstStart:
                cur += ord(s[firstEnd]) - ord('0')
                firstEnd -= 1
            if secondEnd >= secondStart:
                cur += ord(s[secondEnd]) - ord('0')
                secondEnd -= 1
            carry = cur // 10
            cur %= 10
            third.append(chr(cur + ord('0')))
        return ''.join(third[::-1])

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/additive-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。