Longest Code in the World, Accepted Solution.


  • -1
    B
    class Solution(object):
    def isAdditiveNumber(self, num):
        """
        :type num: str
        :rtype: bool
        """
        #1,1,2,3,5,8
        if len(num) <3:
            return False
        num = list(str(int(num)))
        print num, "is NUM"
        beginningOfFirst = 0
        endOfFirst = 1
        endOfSecond = 2
        stack = [(beginningOfFirst, endOfFirst, endOfSecond)]
        noZeroInvolved = True
        backtrack = []
        while stack:
            #print stack
            noZeroInvolved = True
            beginningOfFirst,endOfFirst, endOfSecond = stack.pop()
            print "printing", num[beginningOfFirst:endOfFirst]
            if "0" == num[beginningOfFirst:endOfFirst][0] and int(''.join([str(i) for i in num[beginningOfFirst:endOfFirst]])) != 0:
                noZeroInvolved = False
                print "seeing zero"
            if "0" == num[endOfFirst:endOfSecond][0] and int(''.join([str(i) for i in num[endOfFirst:endOfSecond]])) != 0:
                noZeroInvolved = False
                print "seeing zero"
            firstNum = int(''.join([str(i) for i in num[beginningOfFirst:endOfFirst]]))
            
            secondNum = int(''.join([str(i) for i in num[endOfFirst:endOfSecond]]))
            #print secondNum
            sum = str(firstNum + secondNum)
            foundMatch = False
            for index in range(endOfSecond, len(num)+1):
                print "sum and portion are", sum, ''.join(num[endOfSecond:index])
                if num[endOfSecond:index] and "0" == num[endOfSecond:index][0] and int(''.join(num[endOfSecond:index]))!= 0:
                    noZeroInvolved = False
                    print "zero!"
                if ''.join(num[endOfSecond:index]) and (int(sum) == int( ''.join(num[endOfSecond:index]))):
                    backtrack.append((beginningOfFirst,endOfFirst, endOfSecond))
                    print "here, match"
                    #print sum, num[endOfSecond:index]
                    if noZeroInvolved:
                        print "noZeroInvolved"
                        stack.append((endOfFirst,endOfSecond,index)) 
                        foundMatch = True
                        if index == len(num):
                            return True
                        break
            if not foundMatch:
                print "here"
                if endOfSecond+1 <= len(num):
                    stack.append((beginningOfFirst, endOfFirst, endOfSecond+1))
                else:
                    if endOfFirst +2 <= len(num):
                        stack.append((beginningOfFirst, endOfFirst+1, endOfFirst+2))
            if not stack and backtrack:
                bf, ef, es = backtrack.pop()
                if ef+1 == es:
                    stack.append((bf, ef+1, es+1))
                elif ef+1 != es:
                    stack.append((bf, ef+1, es))
                print (bf, ef, es), "back!!!!!!!!!!!!!!!!!!!!!!!!"
                #if es+1 <= len(num)+1:
                    #stack.append((bf, ef, es+1))
            
        return False

Log in to reply
 

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