Generate Parentheses

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

Backtracking gibt C(n) = (2n)! / ((n+1)! n!) Zeichenfolgen aus, die Catalan-Zahl, die asymptotisch wie 4^n / (n^1.5 √π) wächst. Jede benötigt O(n) zum Erstellen und Kopieren, daher beträgt die Laufzeit 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 Klammerpaare?

Die n-te Catalan-Zahl: 1, 2, 5, 14, 42, 132, 429 und 1.430 für n von 1 bis 8. Jede wohlgeformte Zeichenkette zerfällt in ( A ) B, wobei dieses ) zum ersten ( gehört und A und B zusammen n - 1 Paare enthalten. Die Summation über die Größe von A ergibt die Catalan-Rekursion.

Q: Kann man Generate Parentheses ohne Rekursion lösen?

Ja. Behalte einen Stapel mit Teilzuständen, wobei jeder eine Zeichenfolge mit seinen beiden Zählern ist, und erweitere jeden Zustand nach denselben zwei Regeln. Lege zuerst die Erweiterung mit ) auf den Stapel und danach die mit ( , damit die mit ( zuerst entfernt wird und die Ausgabe sortiert bleibt.

MittelBacktracking Rekursion

+10

Eine Klammerzeichenfolge ist wohlgeformt, wenn beim Lesen von links nach rechts die Anzahl der ) niemals die Anzahl der ( übersteigt 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.

Gegeben eine Ganzzahl n, gib alle wohlgeformten Zeichenfolgen mit n öffnenden und n schließenden Klammern in lexikografischer Reihenfolge zurück, 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 gilt: Die Antwort lautet 1.430 Zeichenfolgen.

Beispiele

Eingabe: n = 3
Ausgabe: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Erklärung: Drei Paare ergeben fünf wohlgeformte Zeichenfolgen. ((())) öffnet zuerst alle drei, daher wird es zuerst sortiert; ()()() schließt jedes Paar sofort und kommt zuletzt.

Eingabe: n = 1
Ausgabe: ["()"]
Erklärung: Ein Paar enthält eine wohlgeformte Zeichenfolge. Die einzige andere Anordnung, )(, schließt, bevor etwas geöffnet ist.

Weiterführende Frage

Kannst du die wohlgeformten Zeichenfolgen für n Paare zählen, ohne sie zu erzeugen?

Tipps

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

0 von 3 geöffnet

Lösung

Nur wenige Zeichenfolgen der Länge 2n sind wohlgeformt: 1.430 von 65.536 für n = 8. Baue jede Zeichenfolge von links nach rechts auf und füge ein Zeichen nur dann hinzu, wenn sich das Präfix noch vervollständigen lässt. Zwei Zähler entscheiden darüber, und wenn du ( vor ) ausprobierst, werden die Zeichenfolgen sortiert ausgegeben.

Erstelle jede Zeichenkette und überprüfe sie dann

Idee

Fülle die 2n Positionen mit allen Kombinationen aus ( und ) – das ergibt 4^n Zeichenfolgen – und behalte die wohlgeformten. Um eine Zeichenfolge zu prüfen, durchlaufe sie mit einem Zähler: plus 1 für (, minus 1 für ). Sie ist wohlgeformt, wenn der Zähler nie unter 0 fällt und am Ende 0 beträgt. Wenn du an jeder Position ( vor ) setzt, werden die Zeichenfolgen in sortierter Reihenfolge aufgelistet.

Das Prüfen jeder Zeichenfolge kostet O(n). Für n = 8 sind das 65.536 Zeichenfolgen für 1.430 Ergebnisse, sodass etwa 98 % der Arbeit verworfen werden; mit jedem zusätzlichen Paar vervierfacht sich die Anzahl.

Algorithmus

Halte einen Puffer mit 2n Zeichen und eine Liste für die Antworten bereit.
fill(pos): Wenn pos gleich 2n ist, speichere den Puffer, wenn er korrekt geformt ist.
Setze andernfalls ( an pos und rufe fill(pos + 1) auf, setze dann dort ) und rufe die Funktion erneut auf.
Zur Prüfung addierst du für jedes ( 1 und subtrahierst für jedes ) 1. Verwirf die Zeichenfolge, wenn der Kontostand unter 0 fällt oder am Ende nicht 0 ist.
Rufe fill(0) auf und gib die gespeicherten Zeichenfolgen zurück.

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 schließenden Klammern zurückverfolgen

Idee

Verschiebe die Prüfung in den Aufbau. Ein Präfix kann genau dann zu einer wohlgeformten Zeichenfolge erweitert werden, wenn es höchstens n öffnende Klammern ( verwendet und niemals mehr schließende als öffnende Klammern enthält. Daher ist ( erlaubt, solange opened < n gilt, und ), solange closed < opened gilt. Bei der Länge 2n betragen beide Anzahlen n, und die Zeichenfolge ist wohlgeformt; es bleibt nichts mehr zu prüfen.

Keine Lösung wird ausgelassen, denn jedes Präfix einer wohlgeformten Zeichenfolge erfüllt beide Regeln. Kein Zweig ist umsonst: Für n = 2 kann der Zweig (( nur zweimal geschlossen werden, was (()) ergibt, und der Zweig () kann nur eine öffnende und eine schließende Klammer hinzufügen, was ()() ergibt. Jede Zeichenfolge entspricht einem Pfad durch den Baum und erscheint daher genau einmal. Da der Zweig ( zuerst kommt, ist die Ausgabe sortiert.

Jedes Blatt ist eine Lösung, daher ist der Aufwand proportional zur Ausgabe: O(4^n / √n).

Algorithmus

Behalte den gerade erstellten String und zwei Zähler, opened und closed, beide auf 0.
Wenn der String die Länge 2n hat, speichere eine Kopie und gib sie zurück.
Wenn opened < n, füge ( hinzu, rufe die Rekursion mit opened + 1 auf und entferne das Zeichen wieder.
Wenn closed < opened, füge ) hinzu, rufe die Rekursion mit closed + 1 auf und entferne das Zeichen wieder.
Beginne mit dem leeren String und gib die gespeicherten Strings zurück.

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

closed < n statt closed < opened für ) zuzulassen. Dadurch entsteht ())(, wobei ein Paar geschlossen wird, das nie geöffnet wurde.
Nur am Ende zu prüfen, ob die Anzahlen übereinstimmen. Dadurch wird )( akzeptiert; der Kontostand muss bei jedem Schritt mindestens 0 betragen.
) vor ( auszuprobieren. Die richtigen Zeichenfolgen werden in umgekehrter Reihenfolge ausgegeben.
Den gemeinsamen Puffer statt einer Kopie zu speichern, wenn Listen oder String-Builder veränderlich sind. Jede gespeicherte Antwort zeigt dann denselben Puffer, den das Backtracking wieder leert.
Die Größe eines fest dimensionierten Ergebnisarrays anhand einer niedrigen Schätzung festzulegen. Für n = 8 gibt es 1.430 Antworten.

Häufige Fragen3

Wie hoch ist die Zeitkomplexität von Generate Parentheses?

Backtracking gibt C(n) = (2n)! / ((n+1)! n!) Zeichenfolgen aus, die Catalan-Zahl, die asymptotisch wie 4^n / (n^1.5 √π) wächst. Jede benötigt O(n) zum Erstellen und Kopieren, daher beträgt die Laufzeit 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 Klammerpaare?

Die n-te Catalan-Zahl: 1, 2, 5, 14, 42, 132, 429 und 1.430 für n von 1 bis 8. Jede wohlgeformte Zeichenkette zerfällt in ( A ) B, wobei dieses ) zum ersten ( gehört und A und B zusammen n - 1 Paare enthalten. Die Summation über die Größe von A ergibt die Catalan-Rekursion.

Kann man Generate Parentheses ohne Rekursion lösen?

Ja. Behalte einen Stapel mit Teilzuständen, wobei jeder eine Zeichenfolge mit seinen beiden Zählern ist, und erweitere jeden Zustand nach denselben zwei Regeln. Lege zuerst die Erweiterung mit ) auf den Stapel und danach die mit (, damit die mit ( zuerst entfernt wird und die Ausgabe sortiert bleibt.

def generateParenthesis(n):
    # Schreibe hier den Code

Test #1

Test #2

Argument

n = 3

Erwartete Ausgabe

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