Generate Parentheses

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

La soluzione con backtracking genera il numero di Catalan C(n) = (2n)! / ((n+1)! n!) di stringhe, che cresce come 4^n / (n^1.5 √π) . Ogni stringa ha lunghezza 2n e la ricerca non spreca mai un ramo, quindi il tempo totale è 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?

Esattamente l’n-esimo numero di Catalan: 1, 2, 5, 14, 42, 132, 429 e 1,430 per n da 1 a 8. Un modo per vederlo: ogni stringa ben formata è ( + A + ) + B, dove la prima ( è abbinata a quella ) , e A e B sono ben formate con n-1 coppie tra loro. Sommando rispetto alla dimensione di A si ottiene la ricorrenza di Catalan.

Q: Perché closed < opened garantisce una stringa valida?

Una stringa diventa non valida esattamente quando arriva un ) senza che prima ci sia una ( non abbinata, cioè quando il conteggio di ) supererebbe quello di ( . Consentire ) solo quando closed < opened impedisce che ciò accada, mentre consentire ( solo quando opened < n fa sì che entrambi i conteggi raggiungano n alla lunghezza 2n . Insieme, le due regole descrivono ogni prefisso di una stringa ben formata.

Q: È possibile risolvere Genera parentesi senza ricorsione?

Sì. Tieni uno stack di stati parziali, ciascuno una stringa con i suoi due contatori, ed estendi uno stato con le stesse due regole. Se inserisci nello stack l’estensione ) prima dell’estensione ( , quella con ( viene rimossa per prima e l’output rimane ordinato. Il lavoro è lo stesso; la gestione passa dallo stack delle chiamate al tuo stack.

MedioBacktracking Ricorsione

+10

Una stringa di parentesi è ben formata quando, leggendola 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.

Ti viene dato un intero n. Restituisci tutte le stringhe ben formate composte da 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 possono essere disposte in cinque modi ben formati. ((())) apre tutte e tre prima di chiuderne una qualsiasi e, poiché ( viene prima nell’ordinamento, è il primo dell’elenco; ()()() chiude subito ogni coppia e viene per ultimo.

Input: n = 1
Output: ["()"]
Spiegazione: Una coppia ha un’unica disposizione ben formata. L’unica altra stringa composta da un ( e un ) è )(, che si chiude prima che qualcosa sia aperto.

+10 test nascosti all’invio

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

Solo una piccola parte delle stringhe di lunghezza 2n è ben formata: 5 delle 64 stringhe per n = 3 e 1.430 delle 65.536 per n = 8. L’idea che risolve il problema è costruire la stringa da sinistra a destra e aggiungere solo caratteri che la mantengono valida, così la ricerca non entra mai in un ramo che non può essere completato. Due contatori determinano cosa è consentito: quanti ( hai inserito e quanti ). Provare ( prima di ) a ogni passaggio fa sì che le stringhe risultino già ordinate.

Costruisci ogni stringa, poi controllala

Intuizione

Il metodo diretto consiste nel riempire le 2n posizioni in ogni modo possibile e conservare le stringhe ben formate. Ogni posizione contiene ( oppure ), quindi ci sono 2^(2n) = 4^n stringhe. Una funzione ricorsiva inserisce ( nella posizione successiva, richiama se stessa, poi vi inserisce ) e si richiama di nuovo; ogni stringa completata viene sottoposta a un controllo.

Il controllo percorre la stringa mantenendo un bilanciamento: più 1 per (, meno 1 per ). La stringa è ben formata quando il bilanciamento non scende mai sotto 0 e termina a 0. Scendere sotto 0 significa trovare un ) senza nulla di aperto da chiudere, come al terzo carattere di ())(.

Provare ( prima di ) in ogni posizione elenca le stringhe in ordine lessicografico, perché ( viene prima di ). Quindi le stringhe conservate sono già ordinate.

Il costo è di 4^n stringhe, ciascuna controllata in O(n). Per n = 8 si tratta di 65,536 stringhe per 1,430 risposte, quindi circa il 98% del lavoro viene scartato. Termina in questo caso perché n è al massimo 8, ma cresce di quattro volte a ogni coppia aggiuntiva e continua a costruire stringhe che iniziano con ), anche se il primo carattere basta già a scartarle.

Algoritmo

Mantieni un buffer di 2n caratteri e una lista per le risposte.
Scrivi fill(pos). Se pos è uguale a 2n, controlla il buffer e salvalo se è ben formato.
Altrimenti inserisci ( in pos e chiama fill(pos + 1), poi inserisci ) lì e chiamala di nuovo.
Per controllare una stringa, aggiungi 1 per ogni ( e sottrai 1 per ogni ). Scartala non appena il bilanciamento scende sotto 0 o se non termina a 0.
Chiama fill(0) e restituisci le stringhe salvate, già ordinate.

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

Risalire ai conteggi delle parentesi aperte e chiuse

Intuizione

Sposta il controllo nella costruzione. Un prefisso può ancora diventare una stringa ben formata esattamente quando valgono due regole: usa al massimo n parentesi aperte e non ha mai più ) che (. Quindi, a ogni passaggio, puoi aggiungere ( mentre opened < n e ) mentre closed < opened. Quando la stringa raggiunge la lunghezza 2n, entrambi i conteggi sono n e la stringa è ben formata, senza che resti nulla da controllare.

Ecco l’intero albero per n = 2. Dalla stringa vuota è consentito solo (, perché non ci sono ancora parentesi aperte. Da ( sono consentite entrambe. Nel ramo ((, opened è già 2, quindi ci sta solo ), per due volte, ottenendo (()). Nel ramo (), non ci sono parentesi aperte, quindi ci sta solo (, poi ), ottenendo ()(). Ogni ramo termina con una risposta: la ricerca non costruisce mai una stringa che deve poi scartare.

Non viene tralasciata nessuna risposta. Ogni prefisso di una stringa ben formata rispetta entrambe le regole, quindi la ricerca non rifiuta mai il carattere successivo necessario a quella stringa, e ogni stringa viene prodotta una sola volta, perché i suoi caratteri descrivono un unico percorso nell’albero. L’ordine funziona come nel primo approccio: due stringhe differiscono per la prima volta nel punto in cui i loro percorsi si dividono, e lì il ramo ( viene esplorato per primo.

Ogni foglia è una risposta e il numero di risposte per n coppie è il numero di Catalan C(n), che cresce come 4^n / (n^1.5 √π). Ogni nodo interno si trova lungo il percorso verso almeno una foglia, quindi ci sono al massimo 2n nodi interni per risposta, e copiare una risposta costa O(n). Il costo totale è O(n × C(n)) = O(4^n / √n): per n = 8, vengono costruite direttamente 1.430 stringhe invece di controllarne 65.536.

Algoritmo

Mantieni la stringa in costruzione e due contatori, opened e closed, entrambi impostati a 0.
Se la stringa ha lunghezza 2n, salvatene una copia e restituiscila.
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, già ordinate perché ( viene provata per prima.

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

Le regole si basano su due confronti, quindi gli errori si nascondono in questi confronti e nell’ordine dei due rami.

Consentire ) quando closed < n invece di closed < opened crea stringhe come ())(, che chiudono una coppia mai aperta.
Verificare soltanto che una stringa contenga tanti ( quanti ) accetta )(. Il bilanciamento deve restare pari o superiore a 0 a ogni passaggio, non solo alla fine.
Provare ) prima di ( produce le stringhe giuste in ordine inverso e il confronto con la risposta ordinata fallisce.
Salvare il buffer condiviso invece di una copia, in un linguaggio in cui gli elenchi o i costruttori di stringhe sono mutabili: ogni risposta salvata punta quindi allo stesso buffer, che il backtracking svuota nuovamente.
Dimensionare un array dei risultati fisso per 2n risposte, o basandosi su una qualsiasi stima ridotta: n = 8 ha 1,430 risposte. Aumenta la dimensione dell’array oppure calcola prima il numero di Catalan.

Domande frequenti4

Qual è la complessità temporale di Generate Parentheses?

La soluzione con backtracking genera il numero di Catalan C(n) = (2n)! / ((n+1)! n!) di stringhe, che cresce come 4^n / (n^1.5 √π). Ogni stringa ha lunghezza 2n e la ricerca non spreca mai un ramo, quindi il tempo totale è 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?

Esattamente l’n-esimo numero di Catalan: 1, 2, 5, 14, 42, 132, 429 e 1,430 per n da 1 a 8. Un modo per vederlo: ogni stringa ben formata è ( + A + ) + B, dove la prima ( è abbinata a quella ), e A e B sono ben formate con n-1 coppie tra loro. Sommando rispetto alla dimensione di A si ottiene la ricorrenza di Catalan.

Perché closed < opened garantisce una stringa valida?

Una stringa diventa non valida esattamente quando arriva un ) senza che prima ci sia una ( non abbinata, cioè quando il conteggio di ) supererebbe quello di (. Consentire ) solo quando closed < opened impedisce che ciò accada, mentre consentire ( solo quando opened < n fa sì che entrambi i conteggi raggiungano n alla lunghezza 2n. Insieme, le due regole descrivono ogni prefisso di una stringa ben formata.

È possibile risolvere Genera parentesi senza ricorsione?

Sì. Tieni uno stack di stati parziali, ciascuno una stringa con i suoi due contatori, ed estendi uno stato con le stesse due regole. Se inserisci nello stack l’estensione ) prima dell’estensione (, quella con ( viene rimossa per prima e l’output rimane ordinato. Il lavoro è lo stesso; la gestione passa dallo stack delle chiamate al tuo stack.

Python

def generateParenthesis(n):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Input

n = 3

Atteso

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