Decode String

+10

Zakodowany ciąg zapisuje powtarzający się tekst jako k[text]: text zapisany k razy z rzędu. Grupy mogą być zagnieżdżone, więc 2[a3[b]] oznacza abbbabbb. Mając zakodowany ciąg s, zwróć zdekodowany ciąg.

Litery znajdujące się poza wszystkimi nawiasami pozostają bez zmian. Każdy licznik jest dodatnią liczbą całkowitą zapisaną bezpośrednio przed [, a cyfry nie występują nigdzie indziej.

Funkcja

decodeString(s: string) → string

sstring: zakodowany ciąg znaków
Zwracastring: zdekodowany ciąg znaków

Ograniczenia

1 ≤ s.length ≤ 10⁴
s zawiera wyłącznie małe litery alfabetu angielskiego, cyfry, [ oraz ].
s jest prawidłowym kodowaniem: po każdym [ występuje liczba, a następnie pasujące ], i żadne nawiasy nie są puste.
Każda liczba k spełnia warunek 1 ≤ k ≤ 300 i nie ma zer wiodących.
Nawiasy mogą być zagnieżdżone na maksymalnie 100 poziomach.
Ciąg po dekodowaniu ma co najwyżej 5 × 10⁴ znaków.

Przykłady

Wejście: s = "2[ab]3[c]x"
Wyjście: "ababcccx"
Wyjaśnienie: 2[ab] daje abab, a 3[c] daje ccc. x znajduje się poza wszystkimi nawiasami i jest kopiowane bez zmian: ababcccx.

Wejście: s = "2[x3[yz]]"
Wyjście: "xyzyzyzxyzyzyz"
Wyjaśnienie: Najpierw odkoduj wnętrze: 3[yz] to yzyzyz, więc zewnętrzne ciało to xyzyzyz. Zapisane dwa razy daje xyzyzyzxyzyzyz.

Wejście: s = "q10[w]e"
Wyjście: "qwwwwwwwwwwe"
Wyjaśnienie: Liczba wynosi 10, odczytywana z dwóch cyfr, więc w pojawia się dziesięć razy między q a e.

Pytanie dodatkowe

Zdekodowany ciąg znaków może być znacznie dłuższy niż dane wejściowe. Jak zwrócić znak na pozycji i bez tworzenia całego ciągu, jeśli jego długość może sięgać 10^18?

Podpowiedzi

Otwieraj je po kolei. Każda zdradza trochę więcej.

Otwarte: 0 z 3

Rozwiązanie

Nie możesz zapisać kopii grupy, dopóki nie znasz jej zawartości, a ta może zawierać więcej grup. Dlatego każda metoda najpierw kończy przetwarzanie najbardziej wewnętrznych grup: przepisuje ciąg od środka na zewnątrz, rekurencyjnie przetwarza każdą zawartość albo przechowuje niedokończone grupy zewnętrzne na stosie. Tutaj n to długość wejścia, m to długość zdekodowanego ciągu, a d to głębokość zagnieżdżenia.

Rozwiń najbardziej wewnętrzną grupę, a następnie powtórz

Intuicja

Znajdź grupę, która nie zawiera żadnej innej grupy, wypisz w jej miejscu jej kopie i poszukaj ponownie. Pierwszy ] zawsze zamyka taką grupę: przed nim nie zamknęła się żadna grupa, więc jej treść nie zawiera nawiasów. Odpowiadający mu [ to najbliższy nawias po jego lewej stronie, a liczba powtórzeń to ciąg cyfr bezpośrednio przed nim. W 2[x3[yz]] najpierw rozwija się 3[yz], dając 2[xyzyzyz], a jeszcze jedno rozwinięcie daje odpowiedź.

Każde rozwinięcie tworzy cały ciąg od nowa. Przy b grupach i wyniku o m znakach oznacza to do b × m kopii: 1,000 grup, które po rozwinięciu dają 50,000 znaków, oznacza do 5 × 10^7.

Algorytm

Znajdź pierwszy ]. Jeśli go nie ma, zwróć ciąg znaków.
Przesuwaj się w lewo do najbliższego [. Tekst między nimi to treść.
Odczytaj cyfry przed tym [ jako liczbę k.
Zastąp wszystko od pierwszej cyfry do ] treścią powtórzoną k razy i powtórz.

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:]

Analiza zstępująca rekurencyjna

Intuicja

Zakodowany ciąg znaków to sekwencja liter i grup, a zawartość grupy jest ponownie zakodowanym ciągiem znaków. Dlatego jedna funkcja, decode, odczytuje znaki ze współdzielonej pozycji, aż napotka ] lub koniec danych wejściowych, wywołując samą siebie dla zawartości każdej grupy. To wywołanie kończy się przy pasującym ], ponieważ każde głębiej położone ] zostało odczytane przez głębsze wywołanie. Dla 2[x3[yz]] najbardziej zagnieżdżone wywołanie zwraca yz, środkowe — xyzyzyz, a zewnętrzne zapisuje ten ciąg dwukrotnie.

Każdy znak wejściowy jest odczytywany raz, ale znak wyjściowy jest kopiowany raz dla każdej otaczającej go grupy: czas O(n + m·d). Rekurencja osiąga głębokość d wywołań.

Algorytm

Używaj jednej pozycji pos, wspólnej dla każdego wywołania, zaczynającej się od 0.
decode() wykonuje pętlę, dopóki pos znajduje się wewnątrz ciągu i nie wskazuje na ].
W przypadku litery dodaj ją i przejdź dalej.
W przypadku cyfry odczytaj całą liczbę k, pomiń [, wywołaj decode() dla treści, pomiń ] i dodaj treść k razy.
Zwróć to, co zostało zbudowane. Pierwsze wywołanie zwraca zdekodowany ciąg.

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()

Jedno przejście ze stosem

Intuicja

Rekurencja przechowuje w ramkach wywołań po jednym niedokończonym fragmencie tekstu dla każdej otwartej grupy. Umieść te fragmenty na własnym stosie, a dekodowanie będzie jedną pętlą. [ zapisuje dotychczas zdekodowany na tym poziomie tekst wraz z jego liczbą i rozpoczyna treść od pustego ciągu. ] zdejmuje te elementy ze stosu i dołącza kopie do zapisanego tekstu. Grupy zamykają się w odwrotnej kolejności do tej, w jakiej zostały otwarte, więc szczyt stosu zawsze odpowiada poziomowi, do którego wraca ].

W 2[x3[yz]] odkładasz na stos kolejno (pusty ciąg, 2), a następnie (x, 3). Pierwsze ] zdejmuje ze stosu (x, 3), a current przyjmuje wartość xyzyzyz; ostatnie zdejmuje ze stosu (pusty ciąg, 2) i podwaja tekst. Złożoność pracy odpowiada rekurencji: O(n + m·d), ale przy głębokim zagnieżdżeniu rośnie lista, a nie stos wywołań.

Algorytm

Zacznij od pustego stosu, pustego current i count = 0.
Po napotkaniu cyfry ustaw count = count × 10 + digit.
Po napotkaniu [ umieść na stosie (current, count), a następnie zresetuj obie wartości.
Po napotkaniu litery dołącz ją do current.
Po napotkaniu ] zdejmij ze stosu (before, k) i ustaw current na before, po którym następuje k kopii current.
Zwróć 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)

Pułapki i przypadki brzegowe

Odczytywanie jednej cyfry jako całego licznika. W q10[w]e licznik wynosi 10; odczytanie tylko cyfry przed [ powoduje, że w powtarza się 0 razy.
Niezresetowanie count do 0 po dodaniu go do stosu. Cyfry z następnej grupy zostaną wtedy dopisane do poprzedniej liczby, więc w 2[a3[b]] wewnętrzny licznik zostanie odczytany jako 23.
Umieszczanie kopii przed zapamiętanym tekstem. ab2[c] to abcc, a nie ccab.
Pomijanie liter na najwyższym poziomie. x w 2[ab]3[c]x należy do wyniku.
Dopisywanie po jednym znaku do niezmiennego ciągu znaków. Każde dopisanie może skopiować cały ciąg, więc utworzenie wyniku o długości 50,000 znaków wymaga ponad miliarda kopii znaków. Zbieraj fragmenty na liście lub w obiekcie do budowania ciągów znaków.

Najczęstsze pytania3

Jaka jest złożoność czasowa Decode String?

Odczytanie danych wejściowych ma złożoność O(n). Każdy znak wyjściowy jest kopiowany raz dla każdej otaczającej go grupy, więc całkowita złożoność wynosi O(n + m·d), gdzie m to zdekodowana długość, a d to głębokość zagnieżdżenia. Gdy każdy licznik wynosi co najmniej 2, liczba kopii nie przekracza 2m. Żadne podejście nie osiąga złożoności lepszej niż O(m), ponieważ odpowiedź ma m znaków.

Czy rozwiązać Decode String za pomocą rekurencji czy stosu?

Oba rozwiązania wykonują tę samą pracę. Rekurencja bezpośrednio odwzorowuje format, ponieważ treść grupy sama jest zakodowanym ciągiem znaków, i często jest najszybsza do napisania. Wersja ze stosem działa w jednej pętli i przechowuje niedokończone poziomy na liście, dzięki czemu dane wejściowe zagnieżdżone na tysiące poziomów nie spowodują przepełnienia stosu wywołań.

Jak obsługiwać liczby składające się z więcej niż jednej cyfry?

Buduj liczbę w miarę jej odczytywania: zacznij od 0 i dla każdej cyfry ustaw count = count × 10 + digit. Gdy pojawi się [, liczba jest kompletna, więc 300[a] daje 300.

def decodeString(s):
    # Wpisz tutaj kod

Test #1

Test #2

Test #3

Argument

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

Oczekiwany wynik

"ababcccx"

Decode String

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Rozwiń najbardziej wewnętrzną grupę, a następnie powtórz

Analiza zstępująca rekurencyjna

Jedno przejście ze stosem

Pułapki i przypadki brzegowe

Najczęstsze pytania3

Podobne zadania