Concise python solution, kinda different from other solutions


  • 0

    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]=='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[0]) + len(seq[1])
        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.


Log in to reply
 

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