Python 35 ms DFS


  • 0
    T

    The idea is simple. We do a DFS to find our two initial values for our tentative answer. These values are in the form of num[0...i] + num[i+1...j] such that 0 < i < j < len(num). These numbers will be first and second, respectively. From here: let num_start = j+1. Recursively, check the validity of the next number, where f_validity(next_number = num[num_start:k+1]) = next_number == first + second where num_start <= k < len(num). If valid, update next_number to k+1 and update our initial values to reflect our most recent addition. Return true if num_start is len(num).

    Runtime should be O(n^3).

    There are a few short circuits in the code, but they aren't essential to the argument.

    class Solution(object):
        def isAdditiveNumber(self, num):
            for i in range(len(num)-2):
                if num[0] == "0" and i > 0 or i > len(num) // 2: return False
                for j in range(i+1, len(num)-1):
                    if j-1 > len(num) // 2 or num[i+1] == "0" and j > i + 1: break
                    num_start = j+1
                    first, second = int(num[0:i+1]), int(num[i+1:j+1])
                    count = 2
                    for k in range(j+1, len(num)):  
                        if num[num_start] == "0" or k - num_start > len(num) // 2 or first + second < int(num[num_start:k+1]): break
                        elif first + second == int(num[num_start:k+1]):
                            first = second
                            second = int(num[num_start:k+1])
                            diff = k+1 - num_start
                            num_start += diff
                            k = num_start - 1
                            count += 1
                            if num_start == len(num) and count >= 3:return True
            return False
    

Log in to reply
 

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