Additive Number

题目描述

Additive number is a string whose digits can form additive sequence.

A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.

For example: "112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.`` 1 + 99 = 100, 99 + 100 = 199`

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.

Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.

Follow up:

How would you handle overflow for very large input integers?

解题方法

这题根据对例子的分析，我们可以发现

  • 数字的长度是不确定的
  • 第一个数字和第二个数字的长度没有关系
  • 如果遇到0的话它必然不是数字的开头

所以我们需要枚举所有的可能性，枚举所有的数字的可能长度，可以使用backtracking的方法，类似于permutation的解法。

而判断第三个数是否在剩下的string里，python有一个方便的method str.startswith()。

注意点

  • 第一个数必然小于总长度的一半，否则第三个数不可能是它的和
  • 结束点在第三个数正好是剩下的string
  • 虽然数字开头不能是0，但是0也是一个有效数字

Solution

class Solution(object):
    def isAdditiveNumber(self, num):
        """
        :type num: str
        :rtype: bool
        """
        def isValid(n):
            return len(n) == 1 or n[0] != "0"

        def dfs(a, b, c):
            d = str(int(a) + int(b))
            if not isValid(d) or not c.startswith(d):
                return False
            if c == d:
                return True
            return dfs(b, d, c[len(d):])

        length = len(num)
        if length < 3:
            return False

        for i in range(1, length/2 + 1):
            for j in range(i+1, length):
                a, b, c = num[:i], num[i:j], num[j:]
                if not isValid(a) or not isValid(b):
                    continue
                if dfs(a, b, c):
                    return True

        return False

Reference