Участник:ArthurSamuelyan/Split Array Into Fibonacci Sequence

Материал из DISCOPAL
Перейти к: навигация, поиск
class Solution(object):
    def splitIntoFibonacci(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        self.F = []
        self.splitIntoFibonacciRec(S, 0)
        return self.F
 
 
    # Пытается разбить строку в последовательность Фибоначчи,
    # продолжающую начатую элементами f1 и f2 (f1 и f2 - строки)
    def splitIntoFibonacciRec(self, S, first):
        if first == len(S) and len(self.F) > 2:
            return True
 
        # Попытаемся подобрать ширину следующего числа
        for width in range(1, len(S)-first+1):
            # Проверим, что нет ведущих нулей
            if S[first] == '0' and width > 1:
                # print "Leading zero!" # Debug
                return False
 
            num = int(S[first:first+width])
            # print num # Debug
            # Проверим, что число укладывается в int32
            if num > 2 ** 31 - 1:
                # print "Num way too big!" # Debug
                return False
 
            if len(self.F) >= 2:
                # Если мы нащупали число, которое больше суммы,
                # прекратить перебор, числа большей ширины будут еще больше
                if num > self.F[-1] + self.F[-2]:
                    # print "Num too big" # Debug
                    return False
 
                if num == self.F[-1] + self.F[-2]:
                    self.F.append(num)
                    if self.splitIntoFibonacciRec(S, first+width):
                        return True
 
                    # Здесь рекурсия провалилась. Нужно подобрать другое число.
                    # Rollback
                    self.F.pop()
 
            else:
                # Безусловно добавляем новое число в массив
                self.F.append(num)
                if self.splitIntoFibonacciRec(S, first+width):
                    return True
 
                # Здесь рекурсия провалилась. Нужно подобрать другое число.
                # Rollback
                self.F.pop()
 
        # Здесь мы перебрали все. Не получилось
        # print "Not found" # Debug
        return False