Код по стрелкам вверх и вниз

Средняя

Кодовый замок принимает код из различных цифр от 1 до 9. Вместо самого кода у вас есть подсказка signs — строка из букв 'I' и 'D' длины n. Код состоит из n + 1 цифр, и для каждой позиции i: - если signs[i] == 'I', то i-я цифра кода меньше следующей; - если signs[i] == 'D', то i-я цифра кода больше следующей. Каждую цифру можно использовать не больше одного раза. Среди всех кодов, подходящих под подсказку, верните наименьший (как строку; все коды одной длины, так что сравнивать можно как числа).

Пример 1

signs="IDI" → '1324'

Нужно a < b > c < d. Ставим 1 первой; вторая цифра должна быть больше третьей, поэтому минимум — 3, затем 2, затем 4: «1324».

Пример 2

signs="DDI" → '3214'

Первые три цифры убывают, поэтому начать с 1 нельзя: самое маленькое — «321», а за ними 4.

Пример 3

signs="I" → '12'

Ограничения

1 ≤ len(signs) ≤ 8
signs состоит только из букв 'I' и 'D'

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Stack Greedy String Backtracking

Вход

signs="IDI"

Ожидается

'1324'

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 72 теста на сервере, включая скрытые.