Python BFS 52ms solution


  • 0
    F

    For this kind of judgement problem, BFS is better than DFS, since we just need to find the first occurrence of additive number then we jump out of the loop. And I add some complicated "if" conditions to ensure that the length of the rest of the num is always larger than the length of the new added num, hence avoid some unnecessary checkings.

    class Solution(object):
    def isAdditiveNumber(self, num):
        stack=collections.deque([])
        for i in xrange(1,len(num)-1):
            for j in xrange(i+1,len(num)):
                for k in xrange(j+1,len(num)+1):
                    if max(i,j-i)<=k-j and (num[i]!='0' or j==i+1) and (num[j]!='0' or k==j+1):
                        stack+=(num[:i], num[i:j], num[j:k], num[k:]),
        while stack:
            num1, num2, num3, nums=stack.popleft()
            if not nums:
                if int(num1)+int(num2)==int(num3):
                    return True
            elif int(num1)+int(num2)==int(num3):
                for i in xrange(1,len(nums)+1):
                    if i+1>=max(len(num3),len(num2)) and (len(nums)-i+1>=i or i==len(nums)) and nums[0]!='0':
                        stack+=(num2, num3, nums[0:i],nums[i:]),
        return False

Log in to reply
 

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