Decode String

+10

Ein kodierter String schreibt wiederholten Text als k[text]: text, das k Mal hintereinander geschrieben wird. Gruppen können verschachtelt sein, daher steht 2[a3[b]] für abbbabbb. Gegeben ist ein kodierter String s; gib den dekodierten String zurück.

Buchstaben außerhalb aller Klammern bleiben unverändert. Jede Anzahl ist eine positive ganze Zahl, die direkt vor ihrem [ steht, und Ziffern kommen sonst nirgendwo vor.

Funktion

decodeString(s: string) → string

sstring: die codierte Zeichenfolge
Gibt zurückstring: die dekodierte Zeichenfolge

Einschränkungen

1 ≤ s.length ≤ 10⁴
s enthält nur englische Kleinbuchstaben, Ziffern, [ und ].
s ist eine gültige Kodierung: Auf jedes [ folgt eine Anzahl und es gibt ein passendes ], und keine Klammern sind leer.
Jeder Zählwert k erfüllt 1 ≤ k ≤ 300 und hat keine führende Null.
Klammern können höchstens 100 Ebenen tief verschachtelt sein.
Die dekodierte Zeichenkette hat höchstens 5 × 10⁴ Zeichen.

Beispiele

Eingabe: s = "2[ab]3[c]x"
Ausgabe: "ababcccx"
Erklärung: 2[ab] ergibt abab und 3[c] ergibt ccc. Das x steht außerhalb jeder Klammer und wird unverändert übernommen: ababcccx.

Eingabe: s = "2[x3[yz]]"
Ausgabe: "xyzyzyzxyzyzyz"
Erklärung: Entschlüssle zuerst den inneren Teil: 3[yz] ist yzyzyz, also ist der äußere Inhalt xyzyzyz. Zweimal geschrieben ergibt das xyzyzyzxyzyzyz.

Eingabe: s = "q10[w]e"
Ausgabe: "qwwwwwwwwwwe"
Erklärung: Die Anzahl ist 10, aus zwei Ziffern abgelesen, also erscheint w zehnmal zwischen q und e.

Weiterführende Frage

Die dekodierte Zeichenfolge kann viel länger als die Eingabe sein. Wie würdest du das Zeichen an Position i zurückgeben, ohne die Zeichenfolge zu erstellen, wenn ihre Länge bis zu 10^18 betragen kann?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Du kannst die Kopien einer Gruppe erst schreiben, wenn du ihren Inhalt kennst, und der Inhalt kann weitere Gruppen enthalten. Deshalb werden bei jedem Ansatz zuerst die innersten Gruppen fertiggestellt: Schreibe den String von innen nach außen um, rufe für jeden Inhalt die Funktion rekursiv auf oder lege die noch nicht abgeschlossenen äußeren Gruppen auf einen Stack. Hier ist n die Länge der Eingabe, m die Länge des dekodierten Strings und d die Verschachtelungstiefe.

Erweitere die innerste Gruppe und wiederhole den Vorgang.

Idee

Suche eine Gruppe, die keine weitere Gruppe enthält, schreibe ihre Wiederholungen an ihrer Stelle aus und suche erneut. Die erste ] schließt immer eine solche Gruppe: Vor ihr wurde noch keine Gruppe geschlossen, also enthält ihr Inhalt keine Klammer. Das zugehörige [ ist das nächste links davon, und die Anzahl ist die Ziffernfolge davor. In 2[x3[yz]] wird zuerst 3[yz] expandiert, wodurch 2[xyzyzyz] entsteht; eine weitere Expansion ergibt die Antwort.

Bei jeder Expansion wird die gesamte Zeichenfolge neu aufgebaut. Bei b Gruppen und einer Ausgabe mit m Zeichen sind das bis zu b × m Kopiervorgänge: 1,000 Gruppen, die zu 50,000 Zeichen dekodiert werden, bedeuten bis zu 5 × 10^7.

Algorithmus

Finde das erste ]. Wenn es keins gibt, gib die Zeichenkette zurück.
Gehe nach links bis zum nächsten [. Der Text dazwischen ist der Inhalt.
Lies die Ziffern vor diesem [ als Anzahl k.
Ersetze alles von der ersten Ziffer bis zum ] durch den Inhalt, der k-mal geschrieben wird, und wiederhole den Vorgang.

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

Rekursiver Abstieg

Idee

Eine kodierte Zeichenfolge ist eine Folge von Buchstaben und Gruppen, und der Inhalt einer Gruppe ist wiederum eine kodierte Zeichenfolge. Eine Funktion, decode, liest daher ab einer gemeinsamen Position, bis sie auf ein ] oder das Ende der Eingabe stößt, und ruft sich für den Inhalt jeder Gruppe selbst auf. Dieser Aufruf stoppt beim passenden ], da jedes weiter innen liegende ] bereits von einem tieferen Aufruf verarbeitet wurde. Für 2[x3[yz]] gibt der innerste Aufruf yz zurück, der mittlere xyzyzyz, und der äußere Aufruf schreibt dies zweimal.

Jedes Eingabezeichen wird einmal gelesen, aber ein Ausgabezeichen wird für jede Gruppe, die es umgibt, einmal kopiert: O(n + m·d) Zeit. Die Rekursion geht d Aufrufe tief.

Algorithmus

Behalte eine Position pos, die von jedem Aufruf gemeinsam verwendet wird und bei 0 beginnt.
decode() läuft weiter, solange sich pos innerhalb des Strings befindet und nicht auf einem ] steht.
Bei einem Buchstaben hänge ihn an und gehe weiter.
Bei einer Ziffer lies die ganze Zahl k, überspringe das [, rufe decode() für den Inhalt auf, überspringe das ] und hänge den Inhalt k Mal an.
Gib zurück, was aufgebaut wurde. Der erste Aufruf gibt den dekodierten String zurück.

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

Ein Durchlauf mit einem Stack

Idee

Die Rekursion hält in ihren Aufrufrahmen für jede offene Gruppe ein unfertiges Textstück bereit. Lege diese Stücke auf einen eigenen Stapel, und das Dekodieren wird zu einer einzigen Schleife. Ein [ speichert den bis dahin auf dieser Ebene dekodierten Text samt Anzahl und beginnt den Rumpf mit leerem Text. Ein ] nimmt beides vom Stapel und hängt die Kopien an den gespeicherten Text an. Gruppen werden in umgekehrter Reihenfolge geschlossen, als sie geöffnet wurden, daher ist die oberste Ebene des Stapels immer die Ebene, zu der ein ] zurückkehrt.

Bei 2[x3[yz]] legst du zuerst (leer, 2) und dann (x, 3) auf den Stapel. Das erste ] nimmt (x, 3) vom Stapel, und current wird zu xyzyzyz; das letzte nimmt (leer, 2) vom Stapel und verdoppelt den Text. Der Aufwand entspricht der Rekursion, O(n + m·d), aber bei tiefer Verschachtelung wächst eine Liste und nicht der Aufrufstapel.

Algorithmus

Beginne mit einem leeren Stapel, einem leeren current und count = 0.
Bei einer Ziffer setze count = count × 10 + digit.
Bei [ lege (current, count) auf den Stapel und setze anschließend beide zurück.
Bei einem Buchstaben hänge ihn an current an.
Bei ] nimm (before, k) vom Stapel und setze current auf before, gefolgt von k Kopien von current.
Gib current zurück.

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)

Stolperfallen und Grenzfälle

Eine Ziffer als gesamte Anzahl lesen. In q10[w]e ist die Anzahl 10; wird nur die Ziffer vor [ genommen, wird w 0-mal wiederholt.
count nach dem Hinzufügen nicht auf 0 zurücksetzen. Die Ziffern der nächsten Gruppe erweitern dann die alte Zahl, sodass 2[a3[b]] die innere Anzahl als 23 liest.
Die Wiederholungen vor den gespeicherten Text setzen. ab2[c] ist abcc, nicht ccab.
Buchstaben auf der obersten Ebene weglassen. Das x in 2[ab]3[c]x gehört in die Antwort.
Bei einer unveränderlichen Zeichenkette jeweils ein Zeichen anhängen. Jeder Anhängevorgang kann die gesamte Zeichenkette kopieren, sodass eine Antwort mit 50.000 Zeichen mehr als eine Milliarde Zeichenkopien verursacht. Sammle die Teile in einer Liste oder einem String-Builder.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Decode String?

Das Einlesen der Eingabe benötigt O(n). Jedes Ausgabezeichen wird für jede Gruppe, die es umgibt, einmal kopiert, sodass der Gesamtaufwand O(n + m·d) beträgt, wobei m die dekodierte Länge und d die Verschachtelungstiefe ist. Wenn jeder Zähler mindestens 2 beträgt, bleibt der Kopieraufwand unter 2m. Kein Ansatz ist besser als O(m), da die Antwort m Zeichen hat.

Solltest du Decode String mit Rekursion oder mit einem Stack lösen?

Beide erledigen dieselbe Aufgabe. Die rekursive Variante folgt direkt dem Format, da der Inhalt einer Gruppe selbst eine codierte Zeichenfolge ist, und lässt sich oft am schnellsten schreiben. Die Stack-Variante läuft in einer Schleife und speichert die noch nicht abgeschlossenen Ebenen in einer Liste, sodass Eingaben mit Tausenden von Verschachtelungsebenen keinen Überlauf des Aufrufstapels verursachen können.

Wie gehst du mit Zählwerten um, die mehr als eine Ziffer haben?

Baue die Zahl beim Lesen auf: Beginne bei 0 und setze für jede Ziffer count = count × 10 + digit. Wenn [ kommt, ist die Zahl vollständig, also ergibt 300[a] 300.

def decodeString(s):
    # Schreibe hier den Code

Test #1

Test #2

Test #3

Argument

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

Erwartete Ausgabe

"ababcccx"

Decode String

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Erweitere die innerste Gruppe und wiederhole den Vorgang.

Rekursiver Abstieg

Ein Durchlauf mit einem Stack

Stolperfallen und Grenzfälle

Häufige Fragen3

Ähnliche Aufgaben