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