Decode String
Ein codierter String schreibt wiederholten Text als k[text], was für text steht, das k-mal hintereinander geschrieben wird. Gruppen können innerhalb anderer Gruppen stehen, daher steht 2[a3[b]] für abbbabbb. Schreibe eine Funktion, die einen codierten String s erhält und den dekodierten String zurückgibt.
Buchstaben außerhalb aller Klammern bleiben unverändert. Jede Anzahl ist eine positive ganze Zahl, die direkt vor ihrem [ steht, und Ziffern kommen nirgendwo sonst vor.
Funktion
- sstring
- die codierte Zeichenfolge
- Gibt zurückstring
- die dekodierte Zeichenfolge
Einschränkungen
1 ≤ s.length ≤ 104senthält ausschließlich englische Kleinbuchstaben, Ziffern,[und].sist eine gültige Kodierung: Auf jede[folgt eine Anzahl, und zu ihr gehört eine passende]; außerdem sind keine Klammern leer.- Jeder Zählwert
kerfüllt1 ≤ k ≤ 300und hat keine führende Null. - Klammern sind höchstens 100 Ebenen tief verschachtelt.
- Die dekodierte Zeichenfolge hat höchstens
5 × 104Zeichen.
Beispiele
- Eingabe
- s = "2[ab]3[c]x"
- Ausgabe
- "ababcccx"
- Erklärung
2[ab]ergibtababund3[c]ergibtccc. Dasxsteht außerhalb aller Klammern und wird daher unverändert übernommen. Das ergibtababcccx.
- Eingabe
- s = "2[x3[yz]]"
- Ausgabe
- "xyzyzyzxyzyzyz"
- Erklärung
- Entschlüssle zuerst den inneren Teil:
3[yz]istyzyzyz, also lautet der Inhalt der äußeren Gruppexyzyzyz. Zweimal geschrieben ergibt dasxyzyzyzxyzyzyz.
- Eingabe
- s = "q10[w]e"
- Ausgabe
- "qwwwwwwwwwwe"
- Erklärung
- Die Anzahl ist
10, aus zwei Ziffern gelesen, daher erscheintwzehnmal zwischenqunde. Code, der nur die Ziffer neben der[liest, würde sie 0-mal wiederholen.
+22 versteckte Tests beim Einreichen
Weiterführende Frage
Die dekodierte Zeichenkette kann viel länger als die Eingabe sein. Wie würdest du nur das Zeichen an Position i der dekodierten Zeichenkette zurückgeben, ohne sie aufzubauen, wenn die dekodierte Länge 10^18 erreichen kann?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Du kannst
3[...]nicht ausschreiben, bevor du weißt, was in den Klammern steht, und darin können weitere Gruppen enthalten sein. Welche Art von Gruppe kannst du immer sofort dekodieren?Eine Gruppe, die keine Gruppe in sich enthält, kann sofort erweitert werden. Arbeite also von innen nach außen. Wenn ein
]eintrifft, ist die Gruppe, die es schließt, vollständig, und du brauchst den Text und die Anzahl, die vor ihrem[gewartet haben.Durchlaufe den Text einmal und behalte dabei den bisher aufgebauten Text und die gerade gelesene Zahl im Blick. Bei
[legst du beides auf einen Stapel und beginnst von vorn. Bei]holst du beides vom Stapel und hängst den aktuellen Text so oft an den zuvor gespeicherten Text an, wie es die gespeicherte Zahl vorgibt. Baue jede Zahl Ziffer für Ziffer auf, damit10und300funktionieren.
Lösung
Die Anzahl steht vor den Klammern, aber du kannst die Kopien erst schreiben, wenn du weißt, was darin steht, und darin können sich weitere Gruppen befinden. Eine Gruppe kann also erst erweitert werden, wenn alle Gruppen in ihr fertig sind. Jeder der folgenden Ansätze ist eine Möglichkeit, zuerst die innersten Gruppen fertigzustellen: Schreibe die Zeichenfolge von innen nach außen um, lass einen rekursiven Aufruf die innere Gruppe vor der äußeren fertigstellen oder speichere die noch nicht abgeschlossenen äußeren Gruppen auf einem Stack. Im Folgenden ist n die Länge der Eingabe, m die Länge der dekodierten Zeichenfolge und d die tiefste Verschachtelungstiefe.
Erweitere die innerste Gruppe und wiederhole den Vorgang
Idee
Entschlüssle die Zeichenfolge so, wie du es auf Papier tun würdest. Finde eine Gruppe, die keine andere Gruppe enthält, schreibe ihre Wiederholungen an ihrer Stelle aus und suche erneut. In 2[x3[yz]] enthält die Gruppe 3[yz] nichts, also wird die Zeichenfolge zu 2[xyzyzyz], und eine weitere Expansion ergibt die Antwort.
Das erste ] in der Zeichenfolge schließt immer eine solche Gruppe. Vor ihm wurde keine andere Gruppe geschlossen, daher kann sich zwischen ihm und seinem [ keine Klammer befinden. Dieses [ ist das nächste links davon, und die Anzahl ist die Ziffernfolge direkt davor. Ersetze die Anzahl, die Klammern und den Inhalt durch den Inhalt, der k-mal geschrieben wird, und wiederhole dies, bis kein ] mehr übrig ist.
Das ist korrekt, aber bei jeder Expansion wird die gesamte Zeichenfolge neu aufgebaut. Bei b Gruppen und einer Zeichenfolge, die auf m Zeichen anwächst, bedeutet das bis zu b × m Zeichenkopien. Der versteckte Test mit etwa 1.300 Gruppen nebeneinander erfordert etwa 25 Millionen Kopien, um 27,688 Zeichen zu erzeugen, obwohl ein einziger Durchlauf über die Eingabe genügen würde.
Algorithmus
- Finde das erste
]in der Zeichenkette. Wenn es keines gibt, ist die Zeichenkette dekodiert: Gib sie zurück. - Gehe von dort aus nach links bis zum nächsten
[. Der Text dazwischen ist der Inhalt der Gruppe. - Gehe weiter nach links über die Ziffern vor diesem
[und lies sie als Anzahlk. - Ersetze alles von der ersten Ziffer bis zum
]durch den Inhalt, derk-mal geschrieben wird. - Gehe zurück zu Schritt 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:]Rekursiver Abstieg
Idee
Das Format ist rekursiv: Eine kodierte Zeichenfolge ist eine Folge aus Buchstaben und Gruppen, und der Inhalt einer Gruppe ist wiederum eine kodierte Zeichenfolge. Schreibe also eine Funktion, decode, die ab einer gemeinsam genutzten Position liest, bis sie das ] erreicht, das ihre Ebene beendet, oder bis zum Ende der Eingabe, und das Gelesene dekodiert zurückgibt.
Wenn decode auf eine Ziffer trifft, liest die Funktion die ganze Zahl, überspringt das [ und ruft sich selbst auf, um den Inhalt zu dekodieren. Dieser Aufruf endet beim passenden ], denn jedes tiefer liegende ] wurde bereits von einem tiefer verschachtelten Aufruf verbraucht. Der aufrufende Code überspringt das ], hängt den Inhalt k Mal an und liest weiter. Bei 2[x3[yz]] liest der äußere Aufruf 2; der nächste Aufruf liest x und 3; ein dritter Aufruf gibt yz zurück; der mittlere Aufruf gibt xyzyzyz zurück; und der äußere Aufruf schreibt es zweimal.
Jedes Eingabezeichen wird einmal gelesen. Der tatsächliche Aufwand entsteht durch das Kopieren: Ein Ausgabezeichen wird für jede Gruppe, die es umgibt, einmal kopiert, daher beträgt die Laufzeit O(n + m·d) bei einer Verschachtelungstiefe d. Die Rekursion erreicht außerdem eine Tiefe von d Aufrufen. Bei 100 Ebenen ist das kein Problem, aber eine sehr tiefe Eingabe kann den Aufrufstapel überlaufen lassen: Python beispielsweise bricht standardmäßig bei 1.000 verschachtelten Aufrufen ab.
Algorithmus
- Behalte eine Position
pos, die von jedem Aufruf gemeinsam verwendet wird und beim ersten Zeichen beginnt. decode()läuft, solangeposinnerhalb der Zeichenfolge 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[, rufedecode()für den Inhalt auf, überspringe das]und hänge den Inhaltk-mal an. - Gib zurück, was aufgebaut wurde. Der erste Aufruf gibt die dekodierte Zeichenfolge 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 Stapel
Idee
Die Rekursion hält in ihren Aufrufrahmen für jede offene Gruppe ein unfertiges Textstück bereit. Stattdessen kannst du diese Stücke auf einem eigenen Stapel ablegen und den String in einer Schleife einlesen.
Verfolge für die aktuelle Ebene zwei Dinge: current, den bisher dekodierten Text, und count, die gerade eingelesene Zahl. Eine Ziffer erweitert count zu count × 10 + digit, sodass 10 und 300 korrekt herauskommen. Ein [ öffnet eine Ebene: Lege current und count auf den Stapel und setze dann beide zurück. Ein Buchstabe wird an current angehängt. Ein ] schließt die Ebene: Hole den gespeicherten Text und die Zahl vom Stapel, und current wird zum gespeicherten Text, gefolgt von count Kopien von current.
Verfolge 2[x3[yz]]. Beim ersten [ legst du (leer, 2) auf den Stapel. Durch das x wird current zu x. Beim zweiten [ legst du (x, 3) auf den Stapel, und yz füllt ein frisches current. Beim ersten ] holst du (x, 3) vom Stapel, sodass current zu xyzyzyz wird. Beim letzten ] holst du (leer, 2) vom Stapel, und current wird zu xyzyzyzxyzyzyz.
Gruppen werden in umgekehrter Reihenfolge geschlossen, in der sie geöffnet wurden. Deshalb entspricht das oberste Element des Stapels immer der Ebene, zu der ] zurückkehrt. Der Aufwand entspricht dem der Rekursion, O(n + m·d), aber tiefe Verschachtelung vergrößert nur eine Liste, niemals den Aufrufstapel.
Algorithmus
- Beginne mit einem leeren Stapel, einem leeren
currentundcount = 0. - Bei einer Ziffer setze
count = count × 10 + digit. - Bei
[lege das Paar (current,count) auf den Stapel und setze anschließendcurrentauf leer undcountauf 0 zurück. - Bei einem Buchstaben hänge ihn an
currentan. - Bei
]nimm (before,k) vom Stapel und setzecurrentaufbefore, gefolgt vonkKopien voncurrent. - Gib nach dem letzten Zeichen
currentzurü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
Die meisten falschen Antworten entstehen dadurch, dass die Anzahl falsch gelesen wird oder der gespeicherte Text an der falschen Stelle landet.
- Eine Ziffer als ganze Anzahl lesen. In
q10[w]eist die Anzahl 10. Code, der nur die Ziffer vor dem[nimmt, wiederholtw0-mal. - Vergessen,
countnach dem Hinzufügen zurückzusetzen. Die Ziffern der nächsten Gruppe werden dann zur alten Zahl addiert, sodass2[a3[b]]die innere Anzahl als 23 liest. - Die Kopien vor den gespeicherten Text setzen. Bei einem
]besteht das Ergebnis aus dem Text vor der Gruppe, gefolgt von den Kopien. Daher istab2[c]abccund nichtccab. - Buchstaben auf der obersten Ebene verlieren. Das
xin2[ab]3[c]xsteht außerhalb aller Klammern und gehört trotzdem zur Antwort. - Zeichen einzeln an eine lange unveränderliche Zeichenkette anhängen. Jeder Anhängevorgang kann die ganze Zeichenkette kopieren, wodurch aus einer Antwort mit 50,000 Zeichen Milliarden von Kopien werden. Sammle die Teile in einer Liste oder einem String-Builder.
Häufige Fragen4
Wie hoch ist die Zeitkomplexität von Decode String?
Das Einlesen der Eingabe benötigt O(n). Beim Erstellen der Ausgabe wird jedes Zeichen für jede Gruppe, in der es enthalten ist, einmal kopiert. Daher beträgt der Gesamtaufwand O(n + m·d), wobei m die dekodierte Länge und d die Verschachtelungstiefe ist. Wenn jede Anzahl mindestens 2 beträgt, ist jede Gruppe höchstens halb so lang wie die Gruppe, die sie umgibt, sodass insgesamt weniger als 2m Kopiervorgänge anfallen. Kein Ansatz kann O(m) unterschreiten, da die Antwort selbst m Zeichen hat.
Solltest du „Decode String“ mit Rekursion oder mit einem Stack lösen?
Beide erledigen dieselbe Aufgabe. Die Rekursion folgt direkt dem Format, da der Inhalt einer Gruppe selbst eine kodierte Zeichenfolge ist, und sie lässt sich in einem Vorstellungsgespräch oft am schnellsten schreiben. Die Stack-Version erledigt dasselbe in einer Schleife und hält die noch nicht abgeschlossenen äußeren Ebenen in einer Liste fest, sodass eine sehr tiefe Verschachtelung nicht zu einem Überlauf des Aufrufstapels führen kann. Wenn der Interviewer nach einer Eingabe fragt, die Tausende von Ebenen tief verschachtelt ist, ist der Stack die Antwort.
Wie gehst du mit Zählungen 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. Setze count sofort auf 0 zurück, nachdem du die Zahl auf den Stapel gelegt hast, sonst werden die Ziffern der nächsten Gruppe zu ihr addiert.
Warum speichert der Stack den Text, der vor jeder Klammer stand?
Wenn sich ein [ öffnet, ist der bis dahin auf dieser Ebene dekodierte Text noch nicht fertig: Die Kopien der Gruppe müssen noch daran angehängt werden. Wenn du ihn auf den Stapel legst, bleibt er sicher, während du den Inhalt ausgehend von einer leeren Zeichenkette dekodierst. Wenn das passende ] kommt, erhältst du den Text durch Herunternehmen vom Stapel zurück und hängst die Kopien daran an.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def decodeString(s):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
s = "2[ab]3[c]x"
Erwartet
"ababcccx"