Problem statement

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

Solution

We can choose two indexes: i < j for first two numbers with O(n^2) possible options. We check that first two strings are valid numbers and then we try to build the rest of the string.

Complexity

Time complexity is O(n) to check one pair of i, j and O(n^3) for full problem. Space complexity is O(n).

Code

class Solution:
    def isAdditiveNumber(self, num):
        S = str(num)
        n = len(S)
        for i in range(1, n):
            for j in range(1, n):
                if i + j >= n: continue
                part1, part2 = S[:i], S[i:i+j]
                if part1[0] == "0" and part1 != "0": continue
                if part2[0] == "0" and part2 != "0": continue
                
                ans = [int(part1), int(part2)]
                k = i + j
                while k < n:
                    nxt = ans[-2] + ans[-1]
                    if S[k:].startswith(str(nxt)):
                        k += len(str(nxt))
                        ans += [nxt]
                    else:
                        break
                        
                if k == n and len(ans) >= 3: return True
                
        return False