Generate Parentheses

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

Die Backtracking-Lösung gibt die Catalan-Zahl C(n) = (2n)! / ((n+1)! n!) an Zeichenfolgen aus, die wie 4^n / (n^1.5 √π) wächst. Jede Zeichenfolge hat die Länge 2n , und die Suche verschwendet nie einen Zweig, daher beträgt die Gesamtlaufzeit O(4^n / √n) . Der zusätzliche Speicherbedarf beträgt O(n) für die aktuelle Zeichenfolge und den Aufrufstapel, zuzüglich der Ausgabe.

Q: Wie viele gültige Klammerzeichenfolgen gibt es für n Paare?

Genau die n-te Catalan-Zahl: 1, 2, 5, 14, 42, 132, 429 und 1,430 für n von 1 bis 8. Eine Möglichkeit, das zu sehen: Jede wohlgeformte Zeichenkette ist ( + A + ) + B, wobei das erste ( durch genau dieses ) gepaart wird und A und B wohlgeformt sind, mit insgesamt n-1 Paaren zwischen ihnen. Die Summierung über die Größe von A ergibt die Catalan-Rekursion.

Q: Warum garantiert geschlossen < geöffnet einen gültigen String?

Ein String gerät genau dann aus der Balance, wenn ein ) eintrifft, ohne dass davor ein nicht zugeordnetes ( steht. Das ist der Fall, wenn die Anzahl der ) die Anzahl der ( übersteigen würde. Wenn ) nur erlaubt ist, solange closed < opened gilt, kann das nie passieren. Wenn ( nur erlaubt ist, solange opened < n gilt, erreichen beide Anzahlen bei der Länge 2n den Wert n . Zusammen beschreiben die beiden Regeln jedes Präfix eines wohlgeformten Strings.

Q: Kann man Parentheses ohne Rekursion lösen?

Ja. Halte einen Stapel mit Teilzuständen bereit, wobei jeder ein String mit seinen beiden Zählern ist, und erweitere einen Zustand mit denselben beiden Regeln. Wenn du die Erweiterung ) vor der Erweiterung ( auf den Stapel legst, wird zuerst die Erweiterung ( entnommen und die Ausgabe bleibt sortiert. Der Aufwand ist derselbe; die Verwaltung wird vom Aufrufstapel auf deinen eigenen Stapel verlagert.

MittelBacktracking Rekursion

+10

Eine Klammerzeichenfolge ist wohlgeformt, wenn die Anzahl der ) beim Lesen von links nach rechts nie größer wird als die Anzahl der ( und beide Anzahlen am Ende gleich sind. Daher ist (())() wohlgeformt, während ())( es nicht ist: Ihr drittes Zeichen schließt ein Paar, das nie geöffnet wurde.

Du erhältst eine ganze Zahl n. Gib alle wohlgeformten Zeichenfolgen aus n öffnenden und n schließenden Klammern zurück, sortiert in lexikografischer Reihenfolge, wobei ( vor ) kommt.

Funktion

generateParenthesis(n: integer) → string-array

ninteger: die Anzahl der Klammerpaare
Gibt zurückstring-array: jede wohlgeformte Zeichenkette aus n Paaren, in lexikografischer Reihenfolge

Einschränkungen

1 ≤ n ≤ 8
Für n = 8 gibt es 1.430 Zeichenfolgen.

Beispiele

Eingabe: n = 3
Ausgabe: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Erklärung: Drei Paare lassen sich auf fünf wohlgeformte Arten anordnen. ((())) öffnet alle drei, bevor eines davon geschlossen wird, und da ( zuerst sortiert wird, steht diese Variante an erster Stelle; ()()() schließt jedes Paar sofort und steht daher an letzter Stelle.

Eingabe: n = 1
Ausgabe: ["()"]
Erklärung: Ein Paar hat genau eine wohlgeformte Anordnung. Die einzige andere Zeichenfolge aus einer ( und einer ) ist )(, die schließt, bevor etwas geöffnet wurde.

+10 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du die korrekt geformten Zeichenfolgen für n Paare zählen, ohne sie zu generieren?

Tipps

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

0 von 3 geöffnet

Lösung

Nur ein kleiner Anteil der Zeichenketten der Länge 2n ist wohlgeformt: 5 der 64 Zeichenketten für n = 3 und 1.430 von 65.536 für n = 8. Der entscheidende Gedanke besteht darin, die Zeichenkette von links nach rechts aufzubauen und jeweils nur ein Zeichen hinzuzufügen, durch das sie gültig bleibt. So gelangt die Suche nie in einen Zweig, der nicht zu Ende geführt werden kann. Zwei Zähler bestimmen, was zulässig ist: wie viele ( du bereits eingefügt hast und wie viele ). Wenn du bei jedem Schritt ( vor ) ausprobierst, sind die Zeichenketten bereits sortiert.

Erstelle jeden String und überprüfe ihn dann

Idee

Die direkte Methode besteht darin, die 2n Positionen auf jede mögliche Weise zu füllen und die wohlgeformten Zeichenfolgen zu behalten. Jede Position enthält ( oder ), also gibt es 2^(2n) = 4^n Zeichenfolgen. Eine rekursive Funktion setzt an der nächsten Position (, ruft sich rekursiv auf, setzt dann dort ) und ruft sich erneut rekursiv auf. Jede fertige Zeichenfolge wird anschließend überprüft.

Bei der Prüfung wird die Zeichenfolge mit einem Zähler durchlaufen: plus 1 für (, minus 1 für ). Die Zeichenfolge ist wohlgeformt, wenn der Zähler nie unter 0 fällt und am Ende 0 beträgt. Ein Abfallen unter 0 bedeutet, dass ein ) nichts Offenes zum Schließen vorfindet, wie beim dritten Zeichen von ())(.

Wenn an jeder Position zuerst ( und dann ) ausprobiert wird, werden die Zeichenfolgen in lexikografischer Reihenfolge aufgelistet, da ( vor ) sortiert wird. Die beibehaltenen Zeichenfolgen sind also bereits sortiert.

Der Aufwand beträgt 4^n Zeichenfolgen, die jeweils in O(n) geprüft werden. Für n = 8 sind das 65.536 Zeichenfolgen für 1.430 Ergebnisse, sodass etwa 98 % der Arbeit verworfen werden. Hier funktioniert es, weil n höchstens 8 beträgt, aber mit jedem zusätzlichen Paar vervierfacht sich der Aufwand. Außerdem werden weiterhin Zeichenfolgen erstellt, die mit ) beginnen, obwohl sie bereits durch das erste Zeichen ausgeschlossen sind.

Algorithmus

Halte einen Puffer mit 2n Zeichen und eine Liste für die Antworten bereit.
Schreibe fill(pos). Wenn pos gleich 2n ist, überprüfe den Puffer und speichere ihn, wenn er wohlgeformt ist.
Setze andernfalls ( an die Stelle pos und rufe fill(pos + 1) auf. Setze dann dort ) und rufe die Funktion erneut auf.
Um eine Zeichenfolge zu überprüfen, addiere für jedes ( 1 und subtrahiere für jedes ) 1. Verwirf sie, sobald der Zähler unter 0 fällt oder am Ende nicht 0 ist.
Rufe fill(0) auf und gib die gespeicherten Zeichenfolgen zurück, die bereits sortiert sind.

def generateParenthesis(n):
    result = []
    path = []

    def is_balanced(text):
        balance = 0
        for ch in text:
            balance += 1 if ch == "(" else -1
            if balance < 0:
                return False  # a ")" with nothing open to close
        return balance == 0

    def fill():
        if len(path) == 2 * n:
            text = "".join(path)
            if is_balanced(text):
                result.append(text)
            return
        for ch in "()":  # "(" first keeps the output sorted
            path.append(ch)
            fill()
            path.pop()

    fill()
    return result

Bei offenen und geschlossenen Anzahlen zurückgehen

Idee

Verlagere die Prüfung in den Aufbau. Ein Präfix kann genau dann noch zu einer wohlgeformten Zeichenkette ergänzt werden, wenn zwei Regeln gelten: Es verwendet höchstens n öffnende Klammern und es gibt nie mehr ) als (. Bei jedem Schritt darfst du also ( hinzufügen, solange opened < n gilt, und ), solange closed < opened gilt. Erreicht die Zeichenkette die Länge 2n, sind beide Zähler n und die Zeichenkette ist wohlgeformt; es bleibt nichts mehr zu prüfen.

Hier ist der vollständige Baum für n = 2. Von der leeren Zeichenkette aus ist nur ( zulässig, da noch nichts geöffnet ist. Von ( aus sind beide zulässig. Im Zweig (( ist opened bereits 2, daher passt nur ), zweimal, wodurch (()) entsteht. Im Zweig () ist nichts geöffnet, daher passt nur (, dann ), wodurch ()() entsteht. Jeder Zweig endet mit einer Lösung: Die Suche baut nie eine Zeichenkette auf, die sie verwerfen muss.

Keine Lösung wird ausgelassen. Jedes Präfix einer wohlgeformten Zeichenkette erfüllt beide Regeln, daher weist die Suche nie das Zeichen zurück, das die Zeichenkette als Nächstes benötigt, und jede Zeichenkette wird genau einmal erzeugt, da ihre Zeichen einen einzigen Pfad durch den Baum vorgeben. Die Reihenfolge funktioniert wie beim ersten Ansatz: Zwei Zeichenketten unterscheiden sich erstmals dort, wo sich ihre Pfade verzweigen, und an dieser Stelle wird zuerst der Zweig ( durchsucht.

Jedes Blatt ist eine Lösung, und die Anzahl der Lösungen für n Paare ist die Catalan-Zahl C(n), die wie 4^n / (n^1.5 √π) wächst. Jeder innere Knoten liegt auf dem Weg zu mindestens einem Blatt, daher gibt es höchstens 2n innere Knoten pro Lösung, und das Kopieren einer Lösung kostet O(n). Insgesamt ergibt das O(n × C(n)) = O(4^n / √n): Für n = 8 werden direkt 1,430 Zeichenketten erzeugt, statt 65,536 geprüft.

Algorithmus

Behalte den gerade aufgebauten String und zwei Zähler, opened und closed, beide auf 0.
Wenn der String die Länge 2n hat, speichere eine Kopie davon und gib sie zurück.
Wenn opened < n, füge ( hinzu, rufe die Funktion rekursiv mit opened + 1 auf und entferne es wieder.
Wenn closed < opened, füge ) hinzu, rufe die Funktion rekursiv mit closed + 1 auf und entferne es wieder.
Beginne mit dem leeren String und gib die gespeicherten Strings zurück; sie sind bereits sortiert, weil zuerst ( ausprobiert wird.

def generateParenthesis(n):
    result = []
    path = []

    def backtrack(opened, closed):
        if len(path) == 2 * n:
            result.append("".join(path))
            return
        # "(" sorts before ")", so trying it first keeps the output sorted
        if opened < n:
            path.append("(")
            backtrack(opened + 1, closed)
            path.pop()
        if closed < opened:  # only close a pair that is open
            path.append(")")
            backtrack(opened, closed + 1)
            path.pop()

    backtrack(0, 0)
    return result

Stolperfallen und Grenzfälle

Die Regeln passen in zwei Vergleiche, daher verbergen sich die Fehler in diesen Vergleichen und in der Reihenfolge der beiden Zweige.

Wenn ) zugelassen wird, solange closed < n gilt, statt closed < opened, entstehen Zeichenfolgen wie ())(, die ein Paar schließen, das nie geöffnet wurde.
Nur zu prüfen, ob eine Zeichenfolge genauso viele ( wie ) enthält, akzeptiert )(. Die Bilanz muss bei jedem Schritt bei 0 oder darüber bleiben, nicht nur am Ende.
Wird ) vor ( ausprobiert, entstehen die richtigen Zeichenfolgen in umgekehrter Reihenfolge, und der Vergleich mit der sortierten Antwort schlägt fehl.
Wird der gemeinsame Puffer statt einer Kopie gespeichert, in einer Sprache, in der Listen oder String-Builder veränderlich sind, verweist jede gespeicherte Antwort auf denselben Puffer, den das Backtracking anschließend wieder leert.
Ein festes Ergebnisarray für 2n Antworten oder irgendeine kleine Schätzung zu dimensionieren, reicht nicht aus: n = 8 ergibt 1,430 Antworten. Vergrößere das Array oder berechne zuerst die Catalan-Zahl.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Generate Parentheses?

Die Backtracking-Lösung gibt die Catalan-Zahl C(n) = (2n)! / ((n+1)! n!) an Zeichenfolgen aus, die wie 4^n / (n^1.5 √π) wächst. Jede Zeichenfolge hat die Länge 2n, und die Suche verschwendet nie einen Zweig, daher beträgt die Gesamtlaufzeit O(4^n / √n). Der zusätzliche Speicherbedarf beträgt O(n) für die aktuelle Zeichenfolge und den Aufrufstapel, zuzüglich der Ausgabe.

Wie viele gültige Klammerzeichenfolgen gibt es für n Paare?

Genau die n-te Catalan-Zahl: 1, 2, 5, 14, 42, 132, 429 und 1,430 für n von 1 bis 8. Eine Möglichkeit, das zu sehen: Jede wohlgeformte Zeichenkette ist ( + A + ) + B, wobei das erste ( durch genau dieses ) gepaart wird und A und B wohlgeformt sind, mit insgesamt n-1 Paaren zwischen ihnen. Die Summierung über die Größe von A ergibt die Catalan-Rekursion.

Warum garantiert geschlossen < geöffnet einen gültigen String?

Ein String gerät genau dann aus der Balance, wenn ein ) eintrifft, ohne dass davor ein nicht zugeordnetes ( steht. Das ist der Fall, wenn die Anzahl der ) die Anzahl der ( übersteigen würde. Wenn ) nur erlaubt ist, solange closed < opened gilt, kann das nie passieren. Wenn ( nur erlaubt ist, solange opened < n gilt, erreichen beide Anzahlen bei der Länge 2n den Wert n. Zusammen beschreiben die beiden Regeln jedes Präfix eines wohlgeformten Strings.

Kann man Parentheses ohne Rekursion lösen?

Ja. Halte einen Stapel mit Teilzuständen bereit, wobei jeder ein String mit seinen beiden Zählern ist, und erweitere einen Zustand mit denselben beiden Regeln. Wenn du die Erweiterung ) vor der Erweiterung ( auf den Stapel legst, wird zuerst die Erweiterung ( entnommen und die Ausgabe bleibt sortiert. Der Aufwand ist derselbe; die Verwaltung wird vom Aufrufstapel auf deinen eigenen Stapel verlagert.

Python

def generateParenthesis(n):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Eingabe

n = 3

Erwartet

["((()))", "(()())", "(())()", "()(())", "()()()"]