Decode String

+10

Закодированная строка записывает повторяющийся текст в виде k[text]: text, записанный k раз подряд. Группы могут быть вложенными, поэтому 2[a3[b]] означает abbbabbb. Для заданной закодированной строки s верните декодированную строку.

Буквы вне всех скобок остаются без изменений. Каждое количество — положительное целое число, записанное непосредственно перед [; цифры больше нигде не встречаются.

Функция

decodeString(s: string) → string

sstring: закодированная строка
Возвращаетstring: декодированная строка

Ограничения

1 ≤ s.length ≤ 10⁴
s содержит только строчные английские буквы, цифры, [ и ].
s — корректное кодирование: за каждой [ следует число, и ей соответствует закрывающая ], а пустых скобок нет.
Каждое значение количества k удовлетворяет условию 1 ≤ k ≤ 300 и не имеет ведущего нуля.
Скобки могут быть вложены не более чем на 100 уровней.
Декодированная строка содержит не более 5 × 10⁴ символов.

Примеры

Ввод: s = "2[ab]3[c]x"
Вывод: "ababcccx"
Пояснение: 2[ab] даёт abab, а 3[c] даёт ccc. x находится за пределами всех скобок и копируется без изменений: ababcccx.

Ввод: s = "2[x3[yz]]"
Вывод: "xyzyzyzxyzyzyz"
Пояснение: Сначала расшифруйте внутреннюю часть: 3[yz] — это yzyzyz, поэтому внешняя часть — xyzyzyz. Если записать её дважды, получится xyzyzyzxyzyzyz.

Ввод: s = "q10[w]e"
Вывод: "qwwwwwwwwwwe"
Пояснение: Количество равно 10, оно читается по двум цифрам, поэтому w встречается десять раз между q и e.

Дополнительный вопрос

Декодированная строка может быть намного длиннее входных данных. Как вернуть символ на позиции i, не создавая строку, если её длина может достигать 10^18?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Нельзя записать копии группы, пока не известно её содержимое, а в нём могут быть другие группы. Поэтому при любом подходе сначала обрабатываются самые внутренние группы: переписывайте строку изнутри наружу, рекурсивно обрабатывайте содержимое каждой группы или храните незавершённые внешние группы в стеке. Здесь n — длина входных данных, m — длина декодированной строки, а d — глубина вложенности.

Раскройте самую внутреннюю группу, затем повторите

Идея

Найдите группу, внутри которой нет других групп, запишите её копии на месте и повторите поиск. Первая ] всегда закрывает такую группу: до неё не закрывалась ни одна группа, поэтому в её теле нет скобок. Ближайшая слева от неё [ — это открывающая скобка этой группы, а количество копий задаёт последовательность цифр перед ней. В 2[x3[yz]] сначала раскрывается 3[yz], получается 2[xyzyzyz], а ещё одно раскрытие даёт ответ.

При каждом раскрытии заново строится вся строка. Если есть b групп, а длина результата — m символов, это до b × m копирований: 1,000 групп, которые декодируются в 50,000 символов, означают до 5 × 10^7.

Алгоритм

Найди первую ]. Если её нет, верни строку.
Двигайся влево до ближайшей [. Текст между ними — это содержимое.
Прочитай цифры перед этой [ как число повторений k.
Замени всё от первой цифры до ] на содержимое, записанное k раз, и повтори.

def decodeString(s):
    # Expand one innermost group at a time until no bracket is left.
    while True:
        close = s.find("]")
        if close == -1:
            return s
        # The first ']' closes a group with no group inside it,
        # and the nearest '[' to its left opens that group.
        open_ = s.rfind("[", 0, close)
        start = open_
        while start > 0 and s[start - 1].isdigit():
            start -= 1
        times = int(s[start:open_])
        s = s[:start] + s[open_ + 1:close] * times + s[close + 1:]

Рекурсивный спуск

Идея

Закодированная строка — это последовательность букв и групп, а тело группы тоже является закодированной строкой. Поэтому одна функция decode читает данные из общей позиции, пока не встретит ] или конец ввода, вызывая себя для тела каждой группы. Этот вызов останавливается на соответствующей ], потому что каждая более глубокая ] была обработана более глубоким вызовом. Для 2[x3[yz]] самый внутренний вызов возвращает yz, средний — xyzyzyz, а внешний записывает эту строку дважды.

Каждый входной символ считывается один раз, но выходной символ копируется по одному разу для каждой окружающей его группы: время O(n + m·d). Глубина рекурсии составляет d вызовов.

Алгоритм

Храните одну позицию pos, общую для каждого вызова, начиная с 0.
decode() выполняет цикл, пока pos находится внутри строки и не указывает на ].
Если это буква, добавьте её и перейдите дальше.
Если это цифра, прочитайте всё число k, пропустите [, вызовите decode() для содержимого, пропустите ] и добавьте содержимое k раз.
Верните то, что было собрано. Первый вызов возвращает декодированную строку.

def decodeString(s):
    pos = 0

    def decode():
        # Read from pos up to the ']' that closes this level, or the end.
        nonlocal pos
        parts = []
        while pos < len(s) and s[pos] != "]":
            if s[pos].isdigit():
                times = 0
                while s[pos].isdigit():
                    times = times * 10 + int(s[pos])
                    pos += 1
                pos += 1          # skip '['
                inner = decode()  # the group's body, fully decoded
                pos += 1          # skip ']'
                parts.append(inner * times)
            else:
                parts.append(s[pos])
                pos += 1
        return "".join(parts)

    return decode()

Один проход со стеком

Идея

Рекурсия хранит в кадрах вызовов по одному незавершённому фрагменту текста для каждой открытой группы. Храни эти фрагменты в собственном стеке — и декодирование превратится в один цикл. Символ [ сохраняет текст, декодированный на этом уровне к данному моменту, вместе с числом повторений и начинает тело с пустой строки. Символ ] извлекает их из стека и добавляет копии к сохранённому тексту. Группы закрываются в обратном порядке относительно того, в котором они открылись, поэтому вершина стека — это всегда уровень, к которому возвращается ].

В 2[x3[yz]] ты помещаешь в стек (пустую строку, 2), затем (x, 3). Первая ] извлекает (x, 3), и current становится равным xyzyzyz; последняя извлекает (пустую строку, 2) и удваивает его. Объём работы соответствует рекурсивному решению: O(n + m·d), но при глубоком вложении растёт список, а не стек вызовов.

Алгоритм

Начните с пустого стека, пустой строки current и count = 0.
При встрече с цифрой задайте count = count × 10 + digit.
При встрече с [ поместите (current, count) в стек, затем сбросьте оба значения.
При встрече с буквой добавьте её к current.
При встрече с ] извлеките из стека (before, k) и задайте current значение, состоящее из before, за которым следуют k копий current.
Верните current.

def decodeString(s):
    stack = []      # one entry per open '[': (the text before it, its count)
    current = []    # pieces of the text at the current level
    count = 0
    for ch in s:
        if ch.isdigit():
            count = count * 10 + int(ch)   # counts can have several digits
        elif ch == "[":
            stack.append((current, count))
            current, count = [], 0
        elif ch == "]":
            before, times = stack.pop()
            before.append("".join(current) * times)
            current = before
        else:
            current.append(ch)
    return "".join(current)

Ловушки и крайние случаи

Чтение одной цифры как всего числа повторений. В q10[w]e число повторений равно 10; если взять только цифру перед [, то w будет повторено 0 раз.
Не сбрасывать count до 0 после помещения его в стек. Тогда цифры следующей группы дополнят старое число, и 2[a3[b]] прочитает внутреннее число повторений как 23.
Помещение копий перед сохранённым текстом. ab2[c] — это abcc, а не ccab.
Удаление букв верхнего уровня. x в 2[ab]3[c]x должно быть в ответе.
Добавление символов по одному к неизменяемой строке. При каждом добавлении может копироваться вся строка, поэтому для ответа из 50,000 символов потребуется более миллиарда копирований символов. Собирайте фрагменты в список или в построитель строк.

Частые вопросы3

Какова временная сложность Decode String?

Чтение входных данных занимает O(n). Каждый символ результата копируется один раз для каждой окружающей его группы, поэтому общая сложность составляет O(n + m·d), где m — длина декодированной строки, а d — глубина вложенности. Если каждый счётчик не меньше 2, количество копирований не превышает 2m. Ни один алгоритм не может работать быстрее, чем за O(m), поскольку ответ содержит m символов.

Решать Decode String с помощью рекурсии или стека?

Оба варианта выполняют одну и ту же работу. Рекурсия напрямую следует формату, поскольку тело группы само является закодированной строкой, и часто её быстрее всего написать. Вариант со стеком выполняется в одном цикле и хранит незавершённые уровни в списке, поэтому входные данные с вложенностью в тысячи уровней не приведут к переполнению стека вызовов.

Как обрабатывать счётчики, значения которых состоят более чем из одной цифры?

Собирайте число по мере чтения: начните с 0 и для каждой цифры задавайте count = count × 10 + digit. Когда встречается [, число готово, поэтому 300[a] дает 300.

def decodeString(s):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

s = "2[ab]3[c]x"

Ожидаемый вывод

"ababcccx"

Decode String

Функция

Ограничения

Примеры

Подсказки

Решение

Раскройте самую внутреннюю группу, затем повторите

Рекурсивный спуск

Один проход со стеком

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи