Additive Number

Intuition

Solution

class Solution:
    def _helper(self, s, x, y):
        if not s:
            return False

        index = len(s)
        while index > 0:
            diff = y - x
            if s[index-len(str(diff)):index] == str(diff):
                index -= len(str(diff))
                x, y = diff, x
            else:
                return False
        return True

    def isAdditiveNumber(self, num: str) -> bool:
        l = len(num)
        for l2 in range(1, l // 2 + 1):
            for l1 in range(1, l - l2):
                y = int(num[l - l2:l])
                x = int(num[l - l2 - l1:l - l2])
                if str(y) != num[l - l2:l] or str(x) != num[l - l2 - l1:l - l2]:
                    continue
                if self._helper(num[:l - l2 - l1], x, y):
                    return True
        return False


def main():
    testcases = [
        ('112358', True),
        ('199100199', True),
        ('113', False),
        ('0', False),
        ('5813', True),
        ('10', False),
        ('1203', False),
        ("199111992", True)
    ]
    for case, target in testcases:
        assert Solution().isAdditiveNumber(case) == target, "%s %s" % (case, target)

    print("All test passed")


if __name__ == '__main__':
    main()