Generate Parentheses

Q: Qual è la complessità temporale di Generate Parentheses?

Il backtracking produce C(n) = (2n)! / ((n+1)! n!) stringhe, il numero di Catalan, che cresce come 4^n / (n^1.5 √π) . Ognuna richiede O(n) per essere costruita e copiata, quindi il tempo è O(4^n / √n) . Lo spazio aggiuntivo è O(n) per la stringa corrente e lo stack delle chiamate, oltre all’output.

Q: Quante stringhe di parentesi valide esistono per n coppie?

Gli n-esimi numeri di Catalan: 1, 2, 5, 14, 42, 132, 429 e 1.430 per n da 1 a 8. Ogni stringa ben formata si scompone come ( A ) B, dove quella ) corrisponde alla prima ( e A e B condividono n - 1 coppie. Sommando rispetto alla dimensione di A si ottiene la ricorrenza di Catalan.

Q: È possibile risolvere Generare parentesi senza ricorsione?

Sì. Mantieni una pila di stati parziali, ciascuno una stringa con i suoi due contatori, ed estendi ogni stato applicando le stesse due regole. Inserisci prima l’estensione ) e poi quella ( , così l’estensione ( viene estratta per prima e l’output rimane ordinato.

MedioBacktracking Ricorsione

+10

Una stringa di parentesi è ben formata quando, letta da sinistra a destra, il numero di ) non supera mai il numero di ( e i due conteggi sono uguali alla fine. Quindi (())() è ben formata, mentre ())( non lo è: il suo terzo carattere chiude una coppia che non era mai stata aperta.

Dato un intero n, restituisci tutte le stringhe ben formate con n parentesi aperte e n parentesi chiuse, ordinate in ordine lessicografico, dove ( precede ).

Funzione

generateParenthesis(n: integer) → string-array

ninteger: il numero di coppie di parentesi
Restituiscestring-array: ogni stringa ben formata di n coppie, in ordine lessicografico

Vincoli

1 ≤ n ≤ 8
Per n = 8, la risposta contiene 1,430 stringhe.

Esempi

Input: n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]
Spiegazione: Tre coppie formano cinque stringhe ben formate. ((())) apre tutte e tre per prime, quindi viene prima; ()()() chiude subito ogni coppia e viene per ultima.

Input: n = 1
Output: ["()"]
Spiegazione: Una coppia contiene una stringa ben formata. L’unica altra disposizione, )(, si chiude prima che qualcosa sia aperto.

Per approfondire

Riesci a contare le stringhe ben formate per n coppie senza generarle?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Poche stringhe di lunghezza 2n sono ben formate: 1.430 su 65.536 per n = 8. Costruisci ogni stringa da sinistra a destra e aggiungi un carattere solo quando il prefisso può ancora essere completato. Due contatori lo determinano, e provare ( prima di ) fa sì che le stringhe risultino ordinate.

Costruisci ogni stringa, poi verificala

Intuizione

Riempi le 2n posizioni con ogni combinazione di ( e ): 4^n stringhe, e tieni quelle ben formate. Per verificare una stringa, percorrila tenendo un bilancio: più 1 per (, meno 1 per ). È ben formata quando il bilancio non scende mai sotto 0 e termina a 0. Posizionando ( prima di ) in ogni posizione, si elencano le stringhe in ordine ordinato.

Verificare ogni stringa costa O(n). Per n = 8 si tratta di 65,536 stringhe per 1,430 risposte, quindi circa il 98% del lavoro viene sprecato, e il numero quadruplica a ogni coppia aggiuntiva.

Algoritmo

Mantieni un buffer di 2n caratteri e una lista per le risposte.
fill(pos): se pos è uguale a 2n, salva il buffer se è ben formato.
Altrimenti inserisci ( in pos e chiama fill(pos + 1), poi inserisci ) lì e chiamala di nuovo.
Per controllare, aggiungi 1 per ogni ( e sottrai 1 per ogni ). Scarta la stringa quando il bilancio scende sotto 0 o non termina a 0.
Chiama fill(0) e restituisci le stringhe salvate.

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

Riconsidera i conteggi delle aperture e delle chiusure

Intuizione

Sposta il controllo all'interno della costruzione. Un prefisso può diventare una stringa ben formata esattamente quando usa al massimo n ( e non ha mai più ) che (. Quindi ( è consentita quando opened < n, e ) quando closed < opened. Alla lunghezza 2n entrambi i conteggi sono n e la stringa è ben formata, senza che resti nulla da controllare.

Non si perde nessuna risposta, perché ogni prefisso di una stringa ben formata rispetta entrambe le regole. Nessun ramo è sprecato: per n = 2, il ramo (( può solo chiudersi due volte, producendo (()), mentre il ramo () può solo aprirsi e chiudersi, producendo ()(). Ogni stringa corrisponde a un percorso nell'albero, quindi compare una sola volta, e il ramo ( viene esplorato per primo, perciò l'output è ordinato.

Ogni foglia è una risposta, quindi il lavoro è proporzionale all'output: O(4^n / √n).

Algoritmo

Mantieni la stringa in costruzione e due contatori, opened e closed, entrambi a 0.
Se la stringa ha lunghezza 2n, salva una copia e restituisci.
Se opened < n, aggiungi (, richiama ricorsivamente con opened + 1 e rimuovilo.
Se closed < opened, aggiungi ), richiama ricorsivamente con closed + 1 e rimuovilo.
Parti dalla stringa vuota e restituisci le stringhe salvate.

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

Trappole e casi limite

Consentire ) mentre closed < n invece di closed < opened. Questo produce ())(, che chiude una coppia mai aperta.
Controllare solo che i conteggi corrispondano alla fine. Questo accetta )(; il bilanciamento deve rimanere pari a 0 o superiore a ogni passaggio.
Provare ) prima di (. Le stringhe corrette vengono generate nell’ordine inverso.
Salvare il buffer condiviso invece di una copia, quando gli elenchi o i costruttori di stringhe sono mutabili. Ogni risposta salvata mostra quindi lo stesso buffer, che il backtracking svuota di nuovo.
Dimensionare un array di risultati fisso basandosi su una stima troppo bassa. n = 8 ha 1.430 risposte.

Domande frequenti3

Qual è la complessità temporale di Generate Parentheses?

Il backtracking produce C(n) = (2n)! / ((n+1)! n!) stringhe, il numero di Catalan, che cresce come 4^n / (n^1.5 √π). Ognuna richiede O(n) per essere costruita e copiata, quindi il tempo è O(4^n / √n). Lo spazio aggiuntivo è O(n) per la stringa corrente e lo stack delle chiamate, oltre all’output.

Quante stringhe di parentesi valide esistono per n coppie?

Gli n-esimi numeri di Catalan: 1, 2, 5, 14, 42, 132, 429 e 1.430 per n da 1 a 8. Ogni stringa ben formata si scompone come ( A ) B, dove quella ) corrisponde alla prima ( e A e B condividono n - 1 coppie. Sommando rispetto alla dimensione di A si ottiene la ricorrenza di Catalan.

È possibile risolvere Generare parentesi senza ricorsione?

Sì. Mantieni una pila di stati parziali, ciascuno una stringa con i suoi due contatori, ed estendi ogni stato applicando le stesse due regole. Inserisci prima l’estensione ) e poi quella (, così l’estensione ( viene estratta per prima e l’output rimane ordinato.

def generateParenthesis(n):
    # Scrivi il codice qui

Test #1

Test #2

Argomento

n = 3

Output atteso

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