Декодирование строки

Декодирование строки

Это классическая задача на работу со стеками. Нужно обработать вложенные скобки и числа перед ними, где каждое число указывает количество повторений строки в скобках.

Анализ задачи

• Вход: строка вида k[str1]k2[str2] где k — число, str — подстрока
• Выход: декодированная строка
• Сложность: нужно обработать вложенные скобки типа 3[a2[c]]

Решение 1: Стек (рекомендуется)

Идея: используем стек для отслеживания чисел, скобок и строк.

def decode(s: str) -> str:
    stack = []
    num = 0
    current_str = ""
    
    for char in s:
        if char.isdigit():
            # Может быть многозначное число
            num = num * 10 + int(char)
        elif char == '[':
            # Сохраняем текущее число и строку на стек
            stack.append((num, current_str))
            num = 0
            current_str = ""
        elif char == ']':
            # Извлекаем из стека и расширяем
            prev_num, prev_str = stack.pop()
            current_str = prev_str + current_str * prev_num
        else:
            # Обычный символ
            current_str += char
    
    return current_str

# Примеры
print(decode("3[a]2[bc]"))      # aaabcbc
print(decode("3[a2[c]]"))        # accaccacc
print(decode("2[abc]3[cd]ef"))   # abcabccdcdcdef
print(decode("10[a]"))           # aaaaaaaaaa
print(decode("2[2[y]pq4[2[jk]e1[z]]]"))  # yyp...complex

Как работает:

1. Проходим по строке символ за символом
2. Если цифра: накапливаем в num (для многозначных чисел)
3. Если [: сохраняем текущее число и строку в стек, обнуляем
4. Если ]: извлекаем из стека, повторяем текущую строку нужное число раз
5. Если буква: добавляем в текущую строку

Временная сложность: O(n) где n — длина результата (каждый символ обрабатывается один раз)

Пространственная сложность: O(d) где d — максимальная глубина вложенности

Решение 2: Рекурсия

Альтернативный подход с рекурсией и указателем.

def decode_recursive(s: str) -> str:
    def helper(index):
        result = ""
        num = 0
        
        while index < len(s):
            char = s[index]
            
            if char.isdigit():
                num = num * 10 + int(char)
            elif char == '[':
                # Рекурсивно декодируем содержимое в скобках
                decoded, index = helper(index + 1)
                result += decoded * num
                num = 0
            elif char == ']':
                # Возвращаем результат и текущий индекс
                return result, index
            else:
                result += char
            
            index += 1
        
        return result, index
    
    return helper(0)[0]

print(decode_recursive("3[a2[c]]"))  # accaccacc

Преимущества рекурсии:

• Более интуитивна для вложенных структур
• Не требует явного стека

Недостатки:

• Может быть медленнее из-за вызовов функций
• Риск переполнения стека при глубокой вложенности

Решение 3: С использованием регулярных выражений

import re

def decode_regex(s: str) -> str:
    # Раскрываем скобки от внутренних к внешним
    while '[' in s:
        # Находим innermost pattern: число[содержимое]
        s = re.sub(r'(\d+)\[([^\[\]]*)\]', 
                   lambda m: m.group(2) * int(m.group(1)), 
                   s)
    return s

print(decode_regex("3[a]2[bc]"))    # aaabcbc
print(decode_regex("3[a2[c]]"))      # accaccacc

Как работает:

• Находит innermost скобки (без вложенных скобок внутри)
• Заменяет на повторённую строку
• Повторяет пока не будут обработаны все скобки

Минусы: может быть медленнее на больших входах, не очень эффективна по памяти

Сравнение решений

Тестовые случаи

assert decode("a") == "a"  # Нет скобок
assert decode("2[a]") == "aa"
assert decode("2[abc]") == "abcabc"
assert decode("3[a2[c]]") == "accaccacc"
assert decode("100[a]") == "a" * 100  # Многозначное число
assert decode("") == ""  # Пустая строка
assert decode("a2[b2[c]d]") == "abccbcccd"

Рекомендация

Используй решение со стеком — оно оптимально по сложности, достаточно читаемо и это классический подход для обработки скобочных структур. Это решение требуется знать на собеседовании и встречается в реальных задачах парсинга и обработки текста.