Longest Valid Parentheses

Q: Esiste una soluzione di programmazione dinamica per il problema delle parentesi valide più lunghe?

Sì. Sia end[i] la lunghezza della sottostringa valida più lunga che termina all'indice i ; è 0 quando s[i] è ( . Se s[i-1] è ( , allora end[i] = end[i-2] + 2 . Se è ) , considera j = i - end[i-1] - 1 , il carattere prima della sequenza che termina a i-1 : quando s[j] è ( , racchiude quella sequenza e end[i] = end[i-1] + 2 + end[j-1] , dove l'ultimo termine unisce una sequenza adiacente sul lato sinistro. La risposta è il valore massimo di end[i] , in tempo e memoria O(n) .

Q: Perché un solo passaggio con i contatori non è sufficiente?

Una scansione da sinistra a destra si azzera solo quando ) supera ( . Una ( in più che non viene mai chiusa mantiene i conteggi diversi per il resto della stringa, quindi la scansione non li vede mai coincidere. In (() termina con 2 parentesi aperte e 1 chiusa e non trova nulla. Leggere da destra a sinistra tratta la ( spaiata come la prima scansione tratta una ) spaiata, quindi le due scansioni insieme coprono ogni sequenza.

DifficileStack Programmazione dinamica

+10

Ti viene data una stringa s composta solo dai caratteri ( e ). Trova la sottostringa più lunga (una sequenza di caratteri consecutivi) ben formata: ogni ( al suo interno è chiusa da una ) successiva al suo interno e le coppie sono annidate correttamente, come in (()()). Restituisci la lunghezza di questa sottostringa, oppure 0 se non compare nemmeno ().

Funzione

longestValidParentheses(s: string) → integer

sstring: una stringa di caratteri ( e )
Restituisceinteger: la lunghezza della sottostringa corretta più lunga, oppure 0 se non ce n'è nessuna

Vincoli

1 ≤ s.length ≤ 6 × 10⁴
Ogni carattere di s è ( oppure ).

Esempi

Input: s = "()(())"
Output: 6
Spiegazione: L'intera stringa è ben formata: () seguita da (()). Due parti ben formate affiancate formano una parte ben formata, quindi la risposta è costituita da tutti e 6 i caratteri.

Input: s = "())((())"
Output: 4
Spiegazione: La ) all'indice 2 non ha una parentesi corrispondente, quindi nessuna risposta può attraversarla, e la ( all'indice 3 non viene mai chiusa. La sequenza più lunga è (()) dall'indice 4 al 7, lunga 4, che supera la () all'inizio.

Input: s = "))(("
Output: 0
Spiegazione: Entrambe le ) vengono prima di entrambe le (, quindi nessuna ( viene mai chiusa. Nessuna sottostringa è ben formata e la risposta è 0.

+21 test nascosti all’invio

Per approfondire

Puoi anche indicare dove inizia la sottostringa ben formata più lunga, scegliendo quella più a sinistra quando ce ne sono diverse della stessa lunghezza?

Suggerimenti

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

0 di 3 aperti

Soluzione

Due cose rendono questo problema più difficile che controllare una singola stringa. Le parti ben formate si uniscono quando si toccano, quindi () e (()) una accanto all'altra contano come un'unica sequenza di 6. E un carattere fuori posto, come il ) in ())(()), interrompe la stringa, perciò nessuna soluzione può attraversarlo. Provare ogni posizione di partenza costa O(n²). La soluzione è ricordare dove è iniziata la sequenza corrente: basta una pila di indici con un marcatore di base in fondo per farlo in un'unica passata, mentre due passate con semplici contatori lo fanno senza usare alcuna pila.

Estendi una sottostringa da ogni punto di partenza

Corretto, ma non termina sui test più grandi

Intuizione

Leggi una sottostringa da sinistra a destra mantenendo un bilancio che aumenta di 1 per ( e diminuisce di 1 per ). La sottostringa è ben formata esattamente quando il bilancio non scende mai sotto 0 e termina a 0. Un valore sotto 0 significa che è arrivata una ) senza nulla da chiudere.

Quindi fissa un punto di partenza e procedi verso destra, aggiornando il bilancio un carattere alla volta. Ogni volta che torna a 0, il tratto dall’inizio fino a qui è ben formato e ne registri la lunghezza. Nel momento in cui scende sotto 0, fermati: quella ) resta senza corrispondenza in ogni tratto più lungo che parte da questo punto. Ogni sottostringa ben formata ha un punto di partenza e provi ogni suo possibile punto di arrivo, quindi non ne perdi nessuna.

Il problema è il costo. In una stringa di 59998 ( seguite da (), il bilancio non scende mai sotto 0, quindi ogni punto di partenza procede fino alla fine: circa n²/2 = 1.8 × 10^9 passaggi per n = 6 × 10^4. I test più grandi sono costruiti così. (Controllare ogni sottostringa da zero invece di estenderla sarebbe ancora peggio: O(n³).)

Algoritmo

Imposta best a 0.
Per ogni inizio, imposta balance a 0 e percorri la fine dall'inizio fino all'ultimo carattere.
Aggiungi 1 per ( e sottrai 1 per ).
Se balance è minore di 0, interrompi questo inizio. Se è 0, aggiorna best con la lunghezza della sequenza end - start + 1.
Restituisci best.

def longestValidParentheses(s):
    best = 0
    for start in range(len(s)):
        balance = 0
        for end in range(start, len(s)):
            balance += 1 if s[end] == "(" else -1
            if balance < 0:
                # A ')' without a partner: no longer run starts here
                break
            if balance == 0:
                best = max(best, end - start + 1)
    return best

Stack di indici con un marcatore di base

Intuizione

Abbinare le parentesi con uno stack è un procedimento familiare: inserisci ogni ( ed estrai un elemento per ogni ). Qui ti servono anche le lunghezze, quindi inserisci gli indici e mantieni un indice in più in fondo allo stack: la base, la posizione appena prima della sequenza in cui ti trovi. All'inizio non è stato letto nulla, quindi la base è -1.

Con (, inserisci il suo indice. Con ), estrai un elemento. Possono accadere due cose. Se lo stack è ora vuoto, hai estratto la base, quindi questa ) non aveva nulla da chiudere. Nessuna sottostringa ben formata può contenerla, e diventa la nuova base: inserisci il suo indice. Altrimenti, l'indice che rimane in cima è l'ultimo carattere prima della sequenza che termina in i: può essere una ( ancora aperta oppure la base. Tutto ciò che viene dopo fino a i è abbinato, e la sequenza non può estendersi più a sinistra, quindi la sua lunghezza è i - top.

Ecco ())((()):

i = 0, (: inserisci 0. Stack [-1, 0].
i = 1, ): estrai 0. In cima c'è -1, quindi la sequenza è 1 - (-1) = 2.
i = 2, ): estrai -1 e lo stack è vuoto. Questa ) non ha una parentesi corrispondente, quindi inserisci 2 come nuova base. Stack [2].
i = 3, 4, 5, tre (: inseriscile. Stack [2, 3, 4, 5].
i = 6, ): estrai 5. In cima c'è 4, quindi la sequenza è 6 - 4 = 2.
i = 7, ): estrai 4. In cima c'è 3, quindi la sequenza è 7 - 3 = 4, la risposta.

La base permette di unire le parti adiacenti. Con ()(()), la prima coppia misura 1 - (-1) = 2, e l'ultima ) estrae l'indice 2 e trova di nuovo -1 in cima, quindi misura 5 - (-1) = 6. Misurare invece a partire dalla ( corrispondente darebbe 4 e non conterebbe la () iniziale. Ogni indice viene inserito ed estratto al massimo una volta, quindi la scansione è O(n) e lo stack può contenere fino a n+1 indici.

Algoritmo

Inizia una pila contenente -1 e imposta best a 0.
Per ogni indice i, inserisci i nella pila se s[i] è (.
Se è ), rimuovi un elemento dalla pila.
Se la pila è ora vuota, inserisci i come nuova base. Altrimenti aggiorna best con i - top.
Restituisci best.

def longestValidParentheses(s):
    # The bottom of the stack is the index just before the current run
    stack = [-1]
    best = 0
    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                # This ')' has no partner: it becomes the new base
                stack.append(i)
            else:
                best = max(best, i - stack[-1])
    return best

Conta le aperture e le chiusure in due passaggi

Intuizione

La pila ti dice solo dove è iniziata la sequenza corrente. Anche due contatori possono farlo. Procedi da sinistra a destra contando opens e closes dall’ultimo reset. Quando sono uguali, tutto ciò che c’è dall’ultimo reset è ben formato e ha lunghezza 2 × closes. Quando closes supera opens, una ) non ha una parentesi corrispondente: è lo stesso momento in cui la pila ha perso la sua base, quindi azzera entrambi i contatori.

Una sola scansione non basta. Una ( che non viene mai chiusa mantiene opens in vantaggio per sempre e i conteggi non tornano mai più uguali. In (() la scansione da sinistra termina con 2 parentesi aperte e 1 chiusa e non segnala nulla, anche se () è proprio lì. Quindi procedi una seconda volta, da destra a sinistra, scambiando i ruoli: azzera quando opens supera closes. Letto al contrario, (() dà prima una parentesi chiusa, poi una aperta (sono uguali: lunghezza 2), poi una parentesi aperta che azzera i contatori. La risposta è il maggiore dei risultati delle due scansioni.

Perché due scansioni individuano ogni sequenza: la sequenza più lunga è delimitata da caratteri che non possono mai essere abbinati, oppure dagli estremi della stringa. Se il suo limite sinistro è una ) spaiata o l’inizio, la scansione da sinistra azzera i contatori proprio dove inizia la sequenza e li vede diventare uguali dove termina. Se il suo limite sinistro è una ( spaiata, il suo limite destro non può essere una ), perché quella ) chiuderebbe la ( spaiata e la sequenza sarebbe più lunga. Quindi il limite destro è una ( spaiata o la fine, e la scansione da destra individua la sequenza allo stesso modo. Ogni scansione legge la stringa una volta usando due interi, quindi il tempo è O(n) e la memoria aggiuntiva è O(1).

Algoritmo

Imposta best a 0 e opens e closes a 0.
Procedi da sinistra a destra, contando ogni carattere. Quando i conteggi sono uguali, aggiorna best con 2 × closes. Quando closes è maggiore, reimposta entrambi a 0.
Reimposta entrambi i contatori, poi procedi da destra a sinistra allo stesso modo, tranne per il fatto che reimposti i contatori quando opens è maggiore.
Restituisci best.

def longestValidParentheses(s):
    best = 0

    # Left to right: more ')' than '(' ends every run that started earlier
    opens = closes = 0
    for ch in s:
        if ch == "(":
            opens += 1
        else:
            closes += 1
        if opens == closes:
            best = max(best, 2 * closes)
        elif closes > opens:
            opens = closes = 0

    # Right to left: catches the runs that an unmatched '(' hid from the first pass
    opens = closes = 0
    for ch in reversed(s):
        if ch == "(":
            opens += 1
        else:
            closes += 1
        if opens == closes:
            best = max(best, 2 * opens)
        elif opens > closes:
            opens = closes = 0

    return best

Trappole e casi limite

La maggior parte delle risposte sbagliate conta le coppie corrette nei posti sbagliati oppure perde l’inizio di una sequenza.

Contare le coppie corrispondenti sull’intera stringa. ())((()) ha 3 coppie, ma non sono tutte consecutive e la risposta è 4, non 6.
Misurare una sequenza a partire dalla ( corrispondente. In ()(()) l’ultimo ) corrisponde all’indice 2, che dà 4 e non conta il () davanti. Misura a partire dall’indice rimasto sullo stack dopo l’estrazione.
Iniziare con uno stack vuoto. Il primo ) di ()) non ha quindi nulla con cui confrontarsi, e una ) senza corrispondenza viene estratta da uno stack vuoto. La base -1 risolve entrambi i problemi.
Eseguire i contatori in una sola direzione. (() restituisce 0 da sinistra a destra e ()) restituisce 0 da destra a sinistra; per entrambi la risposta è 2.
Azzerare i contatori quando sono uguali. Conteggi uguali significano che la sequenza può ancora allungarsi, come in ()(); azzerali solo quando uno dei due conteggi supera l’altro.
In Lua e R le posizioni iniziano da 1, quindi la prima base è 0, non -1.

Domande frequenti4

Qual è la complessità temporale di Longest Valid Parentheses?

Sia la soluzione con stack sia quella con contatore a due passaggi leggono ogni carattere un numero costante di volte, quindi vengono eseguite in tempo O(n). Nel caso peggiore, lo stack richiede O(n) di memoria, ad esempio con una stringa composta solo da (, mentre i contatori richiedono O(1). Provare ogni posizione iniziale richiede O(n²).

Perché lo stack inizia da -1?

La lunghezza della sequenza è l’indice corrente meno l’indice immediatamente precedente alla sequenza. Per una sequenza che inizia all’indice 0, quell’indice precedente è -1, un passo prima della stringa. Inserire prima -1 significa che lo stack non è mai vuoto quando una ) corrispondente misura la lunghezza e, quando una ) senza corrispondenza lo rimuove, quella ) diventa la nuova base.

Esiste una soluzione di programmazione dinamica per il problema delle parentesi valide più lunghe?

Sì. Sia end[i] la lunghezza della sottostringa valida più lunga che termina all'indice i; è 0 quando s[i] è (. Se s[i-1] è (, allora end[i] = end[i-2] + 2. Se è ), considera j = i - end[i-1] - 1, il carattere prima della sequenza che termina a i-1: quando s[j] è (, racchiude quella sequenza e end[i] = end[i-1] + 2 + end[j-1], dove l'ultimo termine unisce una sequenza adiacente sul lato sinistro. La risposta è il valore massimo di end[i], in tempo e memoria O(n).

Perché un solo passaggio con i contatori non è sufficiente?

Una scansione da sinistra a destra si azzera solo quando ) supera (. Una ( in più che non viene mai chiusa mantiene i conteggi diversi per il resto della stringa, quindi la scansione non li vede mai coincidere. In (() termina con 2 parentesi aperte e 1 chiusa e non trova nulla. Leggere da destra a sinistra tratta la ( spaiata come la prima scansione tratta una ) spaiata, quindi le due scansioni insieme coprono ogni sequenza.

Python

def longestValidParentheses(s):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

s = "()(())"

Atteso

Longest Valid Parentheses

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Estendi una sottostringa da ogni punto di partenza

Stack di indici con un marcatore di base

Conta le aperture e le chiusure in due passaggi

Trappole e casi limite

Domande frequenti4

Problemi simili