Сложность: 🟡 Средняя
ℹ️ Описание
Вам дана закодированная строка, верните ее декодированную версию.
В строке используется следующее правило кодирования: k[encoded_string], означает что закодированная внутри квадратных скобок строка должна повторяться ровно k раз. Обратите внимание, что k гарантированно является положительным целым числом.
При этом входная строка всегда гарантированно валидная, то есть в ней нет лишних пробелов и квадратные скобки имеют правильную форму. Кроме того, цифры в строке предназначены только для повторяющихся чисел k. Например, не будет ввода типа 3a или 2[4].
Обратите внимание на то, что закодированные строки могут вкладываться друг в друга.
⚠️ Ограничения
— Длина входной строки находится в диапазоне от 1 до 30
— Входная строка содержит только латинские буквы в нижнем регистре, цифры и квадратные скобки
— Входная строка всегда валидная
— Значения k находятся в диапазоне от 1 до 300
— Длина результирующей строки не превышает 10^5
1️⃣ Пример
Входящие данные
"3[a]2[bc]"
Ответ
"aaabcbc"
2️⃣ Пример
Входящие данные
"3[a2[c]]"
Ответ
"accaccacc"
3️⃣ Пример
Входящие данные
"2[abc]3[cd]ef"
Ответ
"abcabccdcdcdef"
✅ Решение
Эту задачу можно решить рекурсивным способом. Для этого определим следующий алгоритм.
1. Создаем результирующую пустую строку, которая будет использоваться для накопления декодированного результата.
2. Далее перебираем строку посимвольно и проверяем следующие условия:
- Если текущий символ является буквой (от ‘a’ до ‘z’), добавляем его в результат res и переходим к следующему символу.
- Если встречается цифра, это означает начало закодированного блока. Число перед [ (количество повторений) считывается посимвольно. Так как k может быть многозначным числом, используется накопление count в цикле, где каждая новая цифра добавляется к count с учетом ее разрядности (умножение на 10).
3. После определения count и нахождения открывающей скобки [, алгоритм ищет соответствующую закрывающую скобку ]. Это делается с помощью счетчика bracket, который увеличивается при нахождении [ и уменьшается при нахождении ], позволяя обрабатывать вложенные скобки.
4. Как только найдена соответствующая закрывающая скобка, вырезается подстрока между [ и ] и для нее рекурсивно вызывается функция decodeString. Результат этого вызова повторяется count раз и добавляется к итоговому результату res.
5. Индекс i устанавливается на позицию закрывающей скобки, чтобы продолжить обход строки после обработанного блока.
Посмотреть реализацию в блоге
🅾️ Оценка сложности
По времени
O(maxk * n), где maxk — максимальное значение k, а n — длина данной строки s.
По памяти
O(n) — это пространство, используемое для хранения внутреннего стека вызовов для рекурсии. Поскольку мы рекурсивно декодируем каждый вложенный шаблон, максимальная глубина стека рекурсивных вызовов не будет превышать n.
#strings #medium