Short Python recursion solution


  • 0
    X

    Cut string into 3 parts and iterate all possible cuts. For each cut, recursively check if the 3rd part starts with the summation of the first 2 parts.

        def isAdditiveNumber(self, num):
            """
            :type num: str
            :rtype: bool
            """
            
            def helper(v1, v2, num):
                if not num: return True
                sums = str(int(v1) + int(v2))
                ls, ln = len(sums), len(num)
                if ln < ls or (len(v1)>1 and v1.startswith('0')) or (len(v2)>1 and v2.startswith('0')) or num[:ls] != sums: 
                    return False
                else:
                    return helper(v2, sums, num[ls:])
            
            for i in xrange(1, len(num)-1):
                for j in xrange(i+1, len(num)):
                    if helper(num[:i], num[i:j], num[j:]):
                        return True
            return False
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.