basic idea: if the first two numbers in the sequence are defined, the whole complete sequence will be defined.
That's to say, if you choose the first two numbers, you know the whole sequence after that.
Then you can generate the sequence and compare to the given string. If not match, continue and choose another first two numbers.
def isAdditiveNumber(self, num): self.n = len(num) for i in xrange(1,self.n/2+1): if num=='0' and i>1: #handling leading 0's return False j = i+1 while len(num)-j >= max(i,j-i): if not (num[i] == '0' and j-i>1): #handling leading 0's if self.generate_seq([num[:i], num[i:j]]) == num: return True j += 1 return False def generate_seq(self, seq): length = len(seq) + len(seq) while length<self.n: new_s = str(int(seq[-1])+int(seq[-2])) seq.append(new_s) length += len(new_s) return ''.join(seq)
This method does not provide pruning, so it may have lower performance for very long strings, comparing to other O(n^3) methods. but it is easy to implement.