394. Decode String

LeetCode задача 394

Задача

На вход подается закодированная строка, необходимо вернуть её декодированное представление.

Правило кодирования таково: k[encoded_string], где encoded_string - строка внутри квадратных скобок, повторяется ровно k раз. k - это всегда положительное целое число.

Подсказки

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

Подход

Всё, что нам нужно, это итерировать строку символ за символом и обрабатывать четыре случая: числа, буквы и скобки. Мы будем использовать один стек для хранения пар вида (префикс строки, число).

Т.к. число и строка могут быть внутри другой строки (3[a2[c]] = 3 * (a + 2 * c)). То используя стек, в котором можем хранить текущую строку до тех пор пока не увидим закрывающуюся скобку для этой строки.

Например:

1. Число 3
2. Открывается скобка. Мы еще не знаем какая будет строка далее, но открывающаяся [ скобка сообщает, что мы уже точно знаем строку(или ее префикс), которая была до это скобки.

   1. В данном случае при первой скобке строка до нее пустая.

   2. А при первой скобке после 2, строка равна a. Вот эту строку мы и будем складывать с той строкой, которая будет перед следующей открывающейся скобкой.

      1. В таком случае получится начало '' + 3 * ('a' + 2 * ... )
      2. B стек будет следующего вида:

      [
          ['', 3],
          ['a', 2]
      ]
      

      3. Когда доходим до следующей строки и видим скобку закрытия ‘]’, то берем последние данные из стека и складываем предыдущую строку с умноженной текущей строкой.
         1. a + 2*c = acc
         2. '' * 3 * acc

Алгоритм

1. Инициализируем пустой стек и две переменные для текущей строки и текущего числа.
2. Итерируемся по каждому символу в входной строке.
   1. Если символ является числом, определяем всё число (возможно, из нескольких цифр).
   2. Если символ открывающая скобка, добавляем пару (текущая строка, текущее число) в стек и сбрасываем переменные.
   3. Если символ закрывающая скобка, вытаскиваем последнюю пару из стека, и обновляем текущую строку.
   4. Если символ является буквой, добавляем его к текущей строке.

Решение

def decodeString(s: str) -> str:
    stack = []  # стек для пар (строка, число)
    curr_str = ''  # текущая декодированная строка
    curr_num = ''  # текущее число

    for char in s:
        if char.isdigit():
            curr_num += char
        elif char == "[":
            # сохраним, что есть на текущий момент
            stack.append((curr_str, int(curr_num)))
            curr_str = ''
            curr_num = ''
        elif char == "]":
            prev_str, num = stack.pop()
            curr_str = prev_str + num * curr_str
        else:
            curr_str += char

    return curr_str