Задача с собеседования в eBay

Задача с собеседования в eBay Дана закодированная строка. Верните её в раскодированном виде. Правило кодирования: k [ закодированная_строка ], где закодированная_строка внутри квадратных скобок повторяется ровно k раз. Гарантируется, что k - целое положительное число. Считайте, что входная строка всегда корректна: нет лишних пробелов, квадратные скобки сформированы правильно и т.д.. Кроме того, можно считать, что исходные данные не содержат цифр, а цифры используются только для указания числа повторов k . Например, не будет таких входных данных, как 3a или 2[4] . Тестовые примеры сгенерированы так, что длина выходной строки никогда не превысит 10⁵. Пример 1: Input: s = "3[a]2[bc]" Output: "aaabcbc" Пример 2: Input: s = "3[a2[c]]" Output: "accaccacc" Пример 3: Input: s = "2[abc]3[cd]ef" Output: "abcabccdcdcdef" Ограничения: 1 <= s.length <= 30; s состоит из строчных английских букв, цифр и квадратных скобок "[]"; s гарантированно является корректным входом; Все целые числа в s находятся в диапазоне [1, 300]. НАШ ЧАТ АЛГОРИТМИСТОВ Решение Очевидная сложность раскодирования в том, что скобки могут быть вложенными. Сначала должны обрабатываться внутренние скобки, поэтому будем использовать стек для хранения символов и промежуточных результатов. Итерируемся по строке s: Добавляем символ в стек, если он не является закрывающей скобкой. Если же встречаем закрывающую скобку, начинаем собирать подстроку: Пока верхний эл-т стека не является открывающей скобкой: извлекаем символы из стека и добавляем в начало substring. Далее открывающую скобку из стека удаляем: мы обработали содержимое внутри скобок, теперь нужно получить число его повторов, находящееся перед открывающей скобкой. Так как число k может быть многозначным, необходимо извлекать символы до тех пор, пока стек не пуст и верхний эл-т является цифрой. Преобразовываем k в целое число и умножаем подстроку на него, добавляем результат в стек. После того, как строка s будет полностью обработана, возвращаем итоговую строку, содержащую объединённые эл-ты стека. Сложность O(maxK^countK * n) - по времени (где maxK - максимальное значение k, countK - количество вложенных k значений (уровень вложенности), а n - максимальная длина закодированной строки) O(n) - по памяти Код class Solution: def decodeString(self, s: str) -> str: stack = [] for char in s: if char != "]": stack.append(char) else: substring = "" while stack[-1] != "[": substring = stack.pop() + substring stack.pop() k = "" while stack and stack[-1].isdigit(): k = stack.pop() + k stack.append(int(k) * substring) return "".join(stack) @algoses