Valid Parentheses

Q: Wie hoch ist die Zeitkomplexität von Valid Parentheses?

Die Stapellösung benötigt O(n) Zeit, da jedes Zeichen höchstens einmal auf den Stapel gelegt oder von ihm entfernt wird. Im schlimmsten Fall benötigt sie O(n) Speicherplatz: bei einer Zeichenkette, die nur öffnende Zeichen enthält. Das wiederholte Entfernen passender Paare benötigt O(n²) Zeit, da eine tief verschachtelte Zeichenkette pro Durchlauf nur ein Paar verliert.

LeichtStack

+10

Du erhältst eine Zeichenfolge s, die nur aus den Klammerzeichen (, ), [, ], { und } besteht. Gib true zurück, wenn die Klammern ausgeglichen sind: Jede schließende Klammer schließt die zuletzt geöffnete, noch nicht geschlossene Klammer, beide sind von derselben Art, und am Ende bleibt keine Klammer offen. Gib andernfalls false zurück.

Funktion

isValid(s: string) → boolean

sstring: die zu überprüfende Klammerzeichenfolge
Gibt zurückboolean: ob die Klammern ausgeglichen sind

Einschränkungen

1 ≤ s.length ≤ 10⁴
s enthält nur die Zeichen (, ), [, ], { und }.

Beispiele

Eingabe: s = "[]{}()"
Ausgabe: true
Erklärung: Drei Paare stehen nebeneinander, und jedes wird direkt nach dem Öffnen geschlossen.

Eingabe: s = "{(})"
Ausgabe: false
Erklärung: Die } kommt an, während die danach geöffnete ( noch offen ist, und schließt daher die falsche Art von Klammer.

Weiterführende Frage

Wenn die Zeichenfolge nur runde Klammern enthielte, könntest du sie dann mit einem einzigen Zähler statt mit einem Stack und mit zusätzlichem Speicherplatz von O(1) überprüfen?

Lösung

Klammern zu zählen reicht nicht aus: {(}) enthält von jeder öffnenden und schließenden Klammer eine und ist trotzdem fehlerhaft, weil die Reihenfolge wichtig ist. Ein Stack speichert die noch offenen Klammern in der Reihenfolge, in der sie geöffnet wurden, sodass sich der gesamte String in einem Durchlauf mit einem Stack überprüfen lässt.

Wiederholt zusammenpassende Paare entfernen

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Jede ausgeglichene Zeichenkette enthält ein innerstes Klammerpaar ohne Zeichen dazwischen, wie das () in {[()]}. Das Löschen eines benachbarten, zusammengehörigen Klammerpaars ändert nie, ob eine Zeichenkette ausgeglichen ist. Wiederhole also die Löschvorgänge, bis in einer Runde nichts mehr entfernt wird: Eine ausgeglichene Zeichenkette schrumpft auf leer, und bei einer unausgeglichenen bleiben Zeichen übrig, wie es von Anfang an bei {(}) der Fall ist.

Jede Runde durchläuft die gesamte Zeichenkette und erstellt eine neue Kopie, und eine verschachtelte Zeichenkette wie (((...))) verliert pro Runde ein Klammerpaar. Das sind bis zu n/2 Runden mit einem Aufwand von O(n), insgesamt also O(n²).

Algorithmus

Lösche jedes (), [] und {} aus der Zeichenkette.
Wenn in diesem Durchgang nichts gelöscht wurde, halte an.
Wiederhole andernfalls den Vorgang mit der kürzeren Zeichenkette.
Gib true zurück, wenn die Zeichenkette am Ende leer ist, und false, wenn noch eine Klammer übrig ist.

def isValid(s):
    while True:
        # Delete every adjacent matched pair in one round.
        shorter = s.replace("()", "").replace("[]", "").replace("{}", "")
        if shorter == s:
            break  # nothing left to delete
        s = shorter
    return s == ""

Ein Durchlauf mit einem Stapel

Idee

Eine schließende Klammer muss die zuletzt geöffnete Klammer schließen, die noch offen ist. Die zuletzt geöffnete Klammer wird zuerst geschlossen, und genau diese Reihenfolge „zuletzt rein, zuerst raus“ wird von einem Stack verwaltet.

Lege für jede öffnende Klammer die passende schließende Klammer auf den Stack. Eine schließende Klammer muss dann dem obersten Element des Stacks entsprechen. Ein leerer Stack bedeutet, dass es nichts zu schließen gibt; ein anderes oberstes Element bedeutet, dass die falsche Klammerart geschlossen wird, wie es bei } in {(}) der Fall ist, während ) oben liegt. Am Ende wurde alles, was noch auf dem Stack liegt, wie bei ((, geöffnet und nie geschlossen. Jedes Zeichen wird einmal auf den Stack gelegt oder davon entfernt: Laufzeit O(n) und höchstens n Einträge auf dem Stack.

Algorithmus

Erstelle einen leeren Stapel.
Bei einer öffnenden Klammer legst du die passende schließende Klammer auf den Stapel.
Bei einer schließenden Klammer gibst du false zurück, wenn der Stapel leer ist oder sein oberstes Zeichen ein anderes ist; andernfalls entfernst du das oberste Zeichen.
Gib nach dem letzten Zeichen nur dann true zurück, wenn der Stapel leer ist.

def isValid(s):
    closers = {'(': ')', '[': ']', '{': '}'}
    stack = []
    for ch in s:
        if ch in closers:
            stack.append(closers[ch])
        elif not stack or stack.pop() != ch:
            return False
    return not stack

Stolperfallen und Grenzfälle

Jede Klammerart einzeln zählen. {(}) hat übereinstimmende Anzahlen und ist trotzdem ungültig, und )( scheitert allein an der Reihenfolge.
Aus einem leeren Stapel entfernen. Eine Zeichenfolge, die mit einer schließenden Klammer beginnt, zum Beispiel } oder )]}, muss false zurückgeben, statt einen Absturz zu verursachen.
Die abschließende Prüfung überspringen. (([{ trifft nie auf eine falsche schließende Klammer, daher zeigt nur der verbleibende Stapel, dass die Zeichenfolge ungültig ist.
Der Länge vertrauen. Eine ungerade Länge ist immer ungültig, aber eine gerade Länge beweist nichts: (] und ())( sind beide ungültig.
Beim Entfernungsansatz Klammern ungefiltert an einen regulären Ausdruck oder ein Lua-Muster übergeben. ( und [ haben dort eine Bedeutung; verwende eine Ersetzung als Klartext.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Valid Parentheses?

Die Stapellösung benötigt O(n) Zeit, da jedes Zeichen höchstens einmal auf den Stapel gelegt oder von ihm entfernt wird. Im schlimmsten Fall benötigt sie O(n) Speicherplatz: bei einer Zeichenkette, die nur öffnende Zeichen enthält. Das wiederholte Entfernen passender Paare benötigt O(n²) Zeit, da eine tief verschachtelte Zeichenkette pro Durchlauf nur ein Paar verliert.

Warum wird für gültige Klammern ein Stack verwendet?

Klammern können verschachtelt sein, daher muss die zuletzt geöffnete Klammer zuerst geschlossen werden. Ein Stack hält diese Klammer oben, wo du sie in konstanter Zeit lesen und entfernen kannst. Dadurch bleibt die gesamte Prüfung bei O(n).

Ist eine leere Zeichenfolge gültige Klammern?

Ja. Eine leere Zeichenkette hat keine nicht passende Klammer und ist daher ausgeglichen: Der Stapel bleibt leer, und die Entfernungsschleife hat nichts zu entfernen. In diesem Problem hat s immer mindestens ein Zeichen.

def isValid(s):
    # Schreibe hier Code

Test #1

Test #2

Test #3

Argument

s = "[]{}()"

Erwartete Ausgabe

true