Строка с аддитивной последовательностью | Сет-2

Опубликовано: 19 Сентября, 2022

Для заданной строки str задача состоит в том, чтобы определить, содержит ли она аддитивную последовательность или нет. Строка содержит аддитивную последовательность, если ее цифры могут составить последовательность чисел, в которой каждое число является суммой двух предыдущих чисел. Допустимая строка должна содержать не менее трех цифр, чтобы получилась одна аддитивная последовательность.

Примеры:

Input: str = “235813”
Output: true
Explanation : One of the possible sequence is: 2 , 3 , 5 , 8 , 13
where 3 = 1 + 2 , 5 = 3 + 2 , 8 = 5 + 3 and 13 = 8 + 5 .

Input: str = “199100199”
Output: true
Explanation : One of the possible sequence is : 1 , 99 , 100 , 199
where 100 = 99 + 1 , 199 = 100 + 99 gives the additive sequence.

Input: str = “12345678”
Output: false
Explanation: No such sequence possible

Подход: рекурсивный подход обсуждается в Set-1 этой статьи.

Подход с возвратом: Вышеупомянутая проблема может быть решена с использованием возврата следующим образом.

  • Одним из основных требований согласно условиям задачи является проверка того, соответствует ли заданная строка свойству аддитивной последовательности, т.е. каждое число в последовательности является суммой двух предыдущих чисел, и это свойство выполняется для всех чисел в последовательности.
  • Таким образом, нет ограничений на выбор первых двух чисел в последовательности (поскольку для проверки свойства аддитивной последовательности необходимы ровно два числа).
  • Поэтому попробуйте все возможные способы сгенерировать первые два числа в серии и, начиная с третьего числа, провести сравнение, т.е. для сохранения свойства аддитивной последовательности следующее число в серии должно быть суммой двух предыдущих чисел.
    • Таким образом, если в какой-либо момент времени число, сгенерированное до сих пор, превышает сумму двух предыдущих чисел , больше нет необходимости двигаться дальше, потому что это число никогда не будет частью аддитивной последовательности . В этом случае отступите и попробуйте остальные комбинации.
    • Если число, сгенерированное до сих пор, является суммой двух предыдущих чисел, затем повторяется для оставшейся строки, используя два предыдущих числа в качестве ссылки, и если достигается конец строки, а длина аддитивной последовательности (размер вектора) равна больше или равно 3, то данная строка имеет аддитивную последовательность.
    • В момент нахождения аддитивной последовательности пометьте глобальную логическую переменную как истину (чтобы указать, что мы нашли решение и избежать проверки остальных комбинаций).

Ниже приведена реализация вышеописанного.


Временная сложность: O(N*N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ