Найдите выражение минимального значения, вставив оператор сложения или умножения между цифрами данного числа

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

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

Пример :

Input: str = “322”
Output: “3+2*2”
Explanation: The value of above expression is 7 which is minimum possible over the other expressions “3+2+2”, “3*2+2”, “3*3*2”

Input: str = “391118571”
Output: “3+9*1*1*1+8+5+7*1”

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

  • Если строка str содержит символ '0', то:
    • Вставить оператор умножения между каждым символом строки
  • В противном случае создайте строку и сохраните итерацию строки, и если текущий символ str[i] :
    • '1', затем вставьте оператор умножения '*' между текущим и предыдущим символом
    • не «1», затем вставьте оператор сложения «+» между текущим и предыдущим символом

Ниже приведена реализация вышеуказанного подхода:


Временная сложность: O(N)
Вспомогательное пространство: O(N), где N — длина заданной строки.

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