Найдите выражение минимального значения, вставив оператор сложения или умножения между цифрами данного числа
Опубликовано: 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 — длина заданной строки.