10/11/2020

[LeetCode] 306. Additive Number

 Problem : https://leetcode.com/problems/additive-number/

Use DFS approach to verify the sequence.

Time Complexity = O ( N ** 3 )


class Solution:
    def isAdditiveNumber(self, num: str) -> bool:
        def dfs(start, pre, target):
            if start == len(num):
                return True
            
            if num[start] == '0':
                if target == 0:
                    return dfs(start + 1, 0, 0)
                else:
                    return False
            
            for i in range(start+1, len(num) + 1):
                if int(num[start:i]) > target:
                    return False
                
                
                if int(num[start:i]) == target:
                    return dfs(i, target, pre + target)
            
            return False
        
        
        for i in range(1, len(num) - 1):
            for j in range(i+1, len(num)):
                if i > 1 and num[0] == '0':
                    break
                
                a = int(num[:i])
                
                if j - i > 1 and num[i] == '0':
                    continue
                    
                b = int(num[i:j])
                if dfs(j, b, a + b):
                    return True
        
        return False

No comments:

Post a Comment