Decode String

Q: Dlaczego stos przechowuje tekst, który znajdował się przed każdym nawiasem?

Gdy pojawia się otwierający [ , tekst zdekodowany dotąd na tym poziomie nie jest jeszcze gotowy: po nim muszą jeszcze nastąpić kopie grupy. Umieszczenie go na stosie zabezpiecza go podczas dekodowania treści od pustego ciągu. Gdy pojawia się pasujący ] , zdjęcie tekstu ze stosu zwraca go, a ty dopisujesz do niego kopie.

ŚrednieStos Rekurencja

+10

Zakodowany ciąg zapisuje powtarzający się tekst jako k[text], co oznacza text zapisany k razy z rzędu. Grupy mogą znajdować się wewnątrz innych grup, więc 2[a3[b]] oznacza abbbabbb. Napisz funkcję, która otrzymuje zakodowany ciąg s i zwraca zdekodowany ciąg.

Litery znajdujące się poza nawiasami pozostają bez zmian. Każda liczba powtórzeń 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, [ i ].
s to prawidłowe kodowanie: po każdym [ występuje liczba, a nawias ma pasujący ]; żaden nawias nie jest pusty.
Każda liczba k spełnia warunek 1 ≤ k ≤ 300 i nie ma zera wiodącego.
Nawiasy mogą być zagnieżdżone maksymalnie na 100 poziomach.
Odszyfrowany ciąg znaków 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, więc jest kopiowane bez zmian, co daje ababcccx.

Wejście: s = "2[x3[yz]]"
Wyjście: "xyzyzyzxyzyzyz"
Wyjaśnienie: Najpierw odkoduj wnętrze: 3[yz] to yzyzyz, więc zawartość zewnętrznej grupy to xyzyzyz. Zapisana dwukrotnie daje xyzyzyzxyzyzyz.

Wejście: s = "q10[w]e"
Wyjście: "qwwwwwwwwwwe"
Wyjaśnienie: Liczba wynosi 10, odczytane z dwóch cyfr, więc w pojawia się dziesięć razy między q i e. Kod, który odczytuje tylko cyfrę obok [, powtórzyłby ją 0 razy.

+22 ukrytych testów przy wysłaniu

Pytanie dodatkowe

Zdekodowany ciąg może być znacznie dłuższy niż dane wejściowe. Jak zwrócić tylko znak na pozycji i zdekodowanego ciągu, nie tworząc go, gdy jego długość może osiągnąć 10^18?

Podpowiedzi

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

Otwarte: 0 z 3

Rozwiązanie

Liczba występuje przed nawiasami, ale nie możesz zapisać kopii, dopóki nie wiesz, co się w nich znajduje, a w środku mogą znajdować się kolejne grupy. Dlatego grupę można rozwinąć dopiero po zakończeniu pracy nad każdą grupą znajdującą się w jej wnętrzu. Każde z poniższych podejść pozwala najpierw przetworzyć najbardziej zagnieżdżone grupy: przepisać ciąg od środka na zewnątrz, pozwolić wywołaniu rekurencyjnemu zakończyć pracę nad wewnętrzną grupą przed zewnętrzną albo przechowywać niedokończone grupy zewnętrzne na stosie. Poniżej n oznacza długość wejścia, m — długość zdekodowanego ciągu, a d — największą głębokość zagnieżdżenia.

Rozwiń najbardziej zagnieżdżoną grupę, a następnie powtórz

Intuicja

Rozkoduj ciąg tak, jak zrobiłbyś to na kartce. Znajdź grupę, która nie zawiera żadnej innej grupy, wypisz w jej miejscu jej kopie i spójrz ponownie. W 2[x3[yz]] grupa 3[yz] niczego w sobie nie zawiera, więc ciąg zmienia się w 2[xyzyzyz], a jeszcze jedno rozwinięcie daje odpowiedź.

Pierwszy znak ] w ciągu zawsze zamyka taką grupę. Żadna inna grupa nie została wcześniej zamknięta, więc nic między nim a odpowiadającym mu [ nie może być nawiasem. Ten znak [ jest najbliższym po jego lewej stronie, a liczba to ciąg cyfr bezpośrednio przed nim. Zastąp liczbę, nawiasy i zawartość zawartością powtórzoną k razy, a następnie powtarzaj, aż nie pozostanie żaden znak ].

To rozwiązanie jest poprawne, ale przy każdym rozwinięciu buduje od nowa cały ciąg. Przy b grupach i ciągu, który rośnie do m znaków, oznacza to do b × m kopii znaków. Ukryty test z około 1,300 grupami obok siebie wymaga około 25 milionów kopii, aby utworzyć 27,688 znaków, podczas gdy wystarczyłoby jedno przejście przez dane wejściowe.

Algorytm

Znajdź pierwsze ] w ciągu. Jeśli go nie ma, ciąg jest zdekodowany: zwróć go.
Przesuwaj się w lewo od niego do najbliższego [. Tekst między nimi jest treścią grupy.
Przesuwaj się dalej w lewo, przechodząc po cyfrach przed tym [, i odczytaj je jako liczbę powtórzeń k.
Zastąp wszystko od pierwszej cyfry do ] treścią grupy zapisaną k razy.
Wróć do kroku 1.

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

Format jest rekurencyjny: zakodowany ciąg znaków to sekwencja liter i grup, a zawartość grupy jest również zakodowanym ciągiem znaków. Napisz więc jedną funkcję decode, która odczytuje znaki od wspólnej pozycji, aż napotka ] kończący jej poziom albo koniec danych wejściowych, i zwraca odczytaną, zdekodowaną zawartość.

Gdy decode napotka cyfrę, odczytuje całą liczbę, pomija [ i wywołuje samą siebie, aby zdekodować zawartość grupy. To wywołanie zatrzymuje się na pasującym ], ponieważ każde głębiej zagnieżdżone ] zostało już pobrane przez głębsze wywołanie. Wywołanie nadrzędne pomija ], dopisuje zawartość k razy i kontynuuje odczyt. Dla 2[x3[yz]] wywołanie zewnętrzne odczytuje 2; następne wywołanie odczytuje x i 3; trzecie wywołanie zwraca yz; wywołanie pośrednie zwraca xyzyzyz; a zewnętrzne zapisuje ten ciąg dwukrotnie.

Każdy znak wejściowy jest odczytywany raz. Rzeczywisty koszt wiąże się z kopiowaniem: znak wyjściowy jest kopiowany raz dla każdej otaczającej go grupy, więc czas działania wynosi O(n + m·d), gdzie d oznacza głębokość zagnieżdżenia. Rekurencja również sięga d wywołań w głąb. To nie problem przy 100 poziomach, ale bardzo głęboko zagnieżdżone dane wejściowe mogą przepełnić stos wywołań: na przykład Python domyślnie zatrzymuje się po 1,000 zagnieżdżonych wywołaniach.

Algorytm

Zachowuj jedną pozycję pos, wspólną dla każdego wywołania, zaczynającą się od pierwszego znaku.
decode() działa w pętli, dopóki pos znajduje się wewnątrz ciągu i nie wskazuje na ].
Gdy napotkasz literę, dołącz ją i przejdź dalej.
Gdy napotkasz cyfrę, odczytaj całą liczbę k, pomiń [, wywołaj decode() dla zawartości, pomiń ] i dołącz zawartość k razy.
Zwróć to, co zostało utworzone. 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 jeden niedokończony fragment tekstu dla każdej otwartej grupy w swoich ramkach wywołań. Możesz zamiast tego przechowywać te fragmenty na własnym stosie i odczytać ciąg w jednej pętli.

Śledź dwie rzeczy dla bieżącego poziomu: current, dotychczas zdekodowany tekst, oraz count, odczytywaną liczbę. Cyfra rozszerza count według wzoru count × 10 + digit, dzięki czemu poprawnie odczytywane są 10 i 300. Znak [ otwiera poziom: umieść current i count na stosie, a następnie wyzeruj obie wartości. Litera trafia do current. Znak ] zamyka poziom: zdejmij z wierzchu stosu zapisany tekst i liczbę, a następnie ustaw current na zapisany tekst, po którym następuje count kopii current.

Prześledź 2[x3[yz]]. Przy pierwszym [ umieszczasz na stosie (pusty tekst, 2). Znak x sprawia, że current ma wartość x. Przy drugim [ umieszczasz na stosie (x, 3), a yz wypełnia nowy, pusty current. Pierwszy ] zdejmuje ze stosu (x, 3), więc current staje się równy xyzyzyz. Ostatni ] zdejmuje ze stosu (pusty tekst, 2), a current staje się równy xyzyzyzxyzyzyz.

Grupy zamykają się w odwrotnej kolejności niż się otwierają, więc element na szczycie stosu zawsze odpowiada poziomowi, do którego wraca znak ]. Nakład pracy jest taki sam jak w przypadku rekurencji, O(n + m·d), ale głębokie zagnieżdżenie powiększa tylko listę, nigdy stos wywołań.

Algorytm

Zacznij od pustego stosu, pustej zmiennej current i count = 0.
Po napotkaniu cyfry ustaw count = count × 10 + digit.
Po napotkaniu [ umieść parę (current, count) na stosie, a następnie ustaw current na pustą wartość i count na 0.
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 current powtórzone k razy.
Po ostatnim znaku 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

Większość błędnych odpowiedzi wynika z błędnego odczytania liczby powtórzeń albo z tego, gdzie trafia zapisany tekst.

Odczytanie jednej cyfry jako całej liczby powtórzeń. W q10[w]e liczba powtórzeń wynosi 10. Kod, który pobiera tylko cyfrę przed [, powtarza w 0 razy.
Zapomnienie o zresetowaniu count do 0 po umieszczeniu jej na stosie. Cyfry następnej grupy zostaną wtedy dodane do poprzedniej liczby, więc 2[a3[b]] odczyta wewnętrzną liczbę powtórzeń jako 23.
Umieszczenie kopii przed zapisanym tekstem. Po napotkaniu ] wynikiem jest tekst sprzed grupy, a po nim kopie, więc ab2[c] daje abcc, a nie ccab.
Utrata liter na najwyższym poziomie. x w 2[ab]3[c]x znajduje się poza wszystkimi nawiasami i nadal należy do odpowiedzi.
Dodawanie po jednym znaku do długiego, niemodyfikowalnego ciągu znaków. Każde dodanie może skopiować cały ciąg, co zamienia odpowiedź składającą się z 50,000 znaków w miliardy kopii. Zbieraj fragmenty na liście lub użyj konstruktora ciągów znaków.

Najczęstsze pytania4

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

Odczytanie danych wejściowych ma złożoność O(n). Tworzenie wyniku kopiuje każdy znak raz dla każdej grupy, w której się znajduje, więc całkowita złożoność wynosi O(n + m·d), gdzie m to długość zdekodowanego ciągu, a d to głębokość zagnieżdżenia. Gdy każda liczba wynosi co najmniej 2, każda grupa jest najwyżej o połowę krótsza od otaczającej ją grupy, więc łączna liczba kopiowań nie przekracza 2m. Żadne podejście nie może osiągnąć złożoności lepszej niż O(m), ponieważ sama odpowiedź składa się z m znaków.

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

Oba rozwiązania wykonują tę samą pracę. Rekurencja bezpośrednio odzwierciedla format, ponieważ zawartość grupy sama jest zakodowanym ciągiem znaków, i często najszybciej można ją napisać podczas rozmowy kwalifikacyjnej. Wersja ze stosem robi to samo w jednej pętli i przechowuje niedokończone poziomy zewnętrzne na liście, więc bardzo głębokie zagnieżdżenie nie może spowodować przepełnienia stosu wywołań. Jeśli osoba prowadząca rozmowę zapyta o dane wejściowe zagnieżdżone na tysiące poziomów, odpowiedzią jest stos.

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. Zresetuj count do 0 zaraz po umieszczeniu go na stosie, inaczej cyfry z następnej grupy zostaną do niego dodane.

Dlaczego stos przechowuje tekst, który znajdował się przed każdym nawiasem?

Gdy pojawia się otwierający [, tekst zdekodowany dotąd na tym poziomie nie jest jeszcze gotowy: po nim muszą jeszcze nastąpić kopie grupy. Umieszczenie go na stosie zabezpiecza go podczas dekodowania treści od pustego ciągu. Gdy pojawia się pasujący ], zdjęcie tekstu ze stosu zwraca go, a ty dopisujesz do niego kopie.

Python

def decodeString(s):
    # Wpisz kod tutaj

Przypadki testowe

Przypadek 1

Przypadek 2

Przypadek 3

Wejście

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

Oczekiwane

"ababcccx"

Decode String

Funkcja

Ograniczenia

Przykłady

Podpowiedzi

Rozwiązanie

Rozwiń najbardziej zagnieżdżoną grupę, a następnie powtórz

Analiza zstępująca rekurencyjna

Jedno przejście ze stosem

Pułapki i przypadki brzegowe

Najczęstsze pytania4

Podobne zadania