Valid Parentheses
Ricevi una stringa s composta solo dai caratteri parentesi (, ), [, ], { e }. Restituisci true quando le parentesi sono bilanciate: ogni parentesi di chiusura chiude la parentesi ancora aperta più recente, le due sono dello stesso tipo e alla fine non rimane nulla di aperto. Altrimenti restituisci false.
Funzione
- sstring
- la stringa di parentesi da controllare
- Restituisceboolean
- se le parentesi sono bilanciate
Vincoli
1 ≤ s.length ≤ 104scontiene solo i caratteri(,),[,],{e}.
Esempi
- Input
- s = "[]{}()"
- Output
- true
- Spiegazione
- Tre coppie stanno una accanto all’altra e ciascuna si chiude subito dopo essersi aperta.
- Input
- s = "{[()()]}"
- Output
- true
- Spiegazione
- Le due coppie di parentesi tonde si chiudono all’interno della coppia di parentesi quadre, che si chiude all’interno della coppia di parentesi graffe. Ogni parentesi di chiusura corrisponde alla parentesi di apertura più recente ancora aperta.
- Input
- s = "{(})"
- Output
- false
- Spiegazione
}arriva mentre la(aperta dopo di essa è ancora aperta, quindi chiude il tipo sbagliato di parentesi.
Per approfondire
Se la stringa contenesse solo parentesi tonde, potresti verificarla con un solo contatore invece di uno stack, usando O(1) spazio aggiuntivo?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Leggi la stringa da sinistra a destra. Quando arriva una parentesi di chiusura, quale parentesi di apertura può chiudere?
Può chiudere solo la parentesi aperta più di recente e ancora aperta. L'ultima aperta è la prima a essere chiusa: è esattamente l'ordine che mantiene uno stack.
Inserisci ogni parentesi di apertura in una pila. Quando incontri una parentesi di chiusura, la pila non deve essere vuota e l'elemento in cima deve essere dello stesso tipo; rimuovilo e continua. Quando la stringa termina, è bilanciata solo se la pila è vuota.
Soluzione
Contare le parentesi non basta: {(}) contiene lo stesso numero di parentesi aperte e chiuse, ma è comunque errata, perché l'ordine è importante. Una pila mantiene le parentesi ancora aperte nell'ordine in cui sono state aperte, così una sola scansione con una pila basta a determinare se l'intera stringa è corretta.
Rimuovi ripetutamente le coppie corrispondenti
Corretto, ma non termina sui test più grandi
Intuizione
Ogni stringa bilanciata ha una coppia più interna senza nulla tra le parentesi, come () dentro {[()]}. Eliminare una coppia adiacente corrispondente non cambia mai se una stringa è bilanciata. Quindi ripeti le eliminazioni finché un passaggio non rimuove nulla: una stringa bilanciata si riduce a vuota, mentre una non bilanciata si blocca con dei caratteri rimasti, come accade fin dall’inizio con {(}).
Ogni passaggio esamina l’intera stringa e costruisce una nuova copia, e una stringa annidata come (((...))) perde una coppia per passaggio. Si arriva fino a n/2 passaggi da O(n) di lavoro, cioè O(n²) in totale.
Algoritmo
- Elimina ogni
(),[]e{}dalla stringa. - Se in quel passaggio non è stato eliminato nulla, fermati.
- Altrimenti ripeti con la stringa più corta.
- Restituisci
truese la stringa è diventata vuota efalsese è rimasta una parentesi.
def isValid(s):
while True:
# Delete every adjacent matched pair in one round.
shorter = s.replace("()", "").replace("[]", "").replace("{}", "")
if shorter == s:
break # nothing left to delete
s = shorter
return s == ""Un passaggio con uno stack
Intuizione
Una parentesi di chiusura deve chiudere la parentesi aperta più di recente che è ancora aperta. L’ultima parentesi aperta è la prima a essere chiusa, e questo ordine LIFO è esattamente ciò che mantiene una pila.
Inserisci nella pila la parentesi di chiusura che ogni parentesi di apertura aspetta. Una parentesi di chiusura deve quindi essere uguale all’elemento in cima alla pila. Una pila vuota significa che non c’è nulla da chiudere; un elemento in cima diverso significa che viene chiuso il tipo sbagliato, come accade con } in {(}) mentre ) è in cima. Alla fine, qualsiasi elemento rimasto nella pila, come in ((, è stato aperto e non è mai stato chiuso. Ogni carattere viene inserito o rimosso una sola volta: tempo O(n) e al massimo n elementi nella pila.
Algoritmo
- Crea uno stack vuoto.
- Per una parentesi di apertura, inserisci la parentesi corrispondente.
- Per una parentesi di chiusura, restituisci
falsese lo stack è vuoto o se in cima c'è un carattere diverso; altrimenti rimuovi l'elemento in cima. - Dopo l'ultimo carattere, restituisci
truesolo se lo stack è vuoto.
def isValid(s):
closers = {'(': ')', '[': ']', '{': '}'}
stack = []
for ch in s:
if ch in closers:
stack.append(closers[ch])
elif not stack or stack.pop() != ch:
return False
return not stack
Trappole e casi limite
- Contare ogni tipo di parentesi.
{(})ha lo stesso numero di parentesi aperte e chiuse, ma non è comunque valido;)(non è valido solo per l’ordine. - Rimuovere elementi da uno stack vuoto. Una stringa che inizia con una parentesi di chiusura, come
}o)]}, deve restituirefalseinvece di causare un arresto anomalo. - Saltare il controllo finale.
(([{non incontra mai una parentesi di chiusura errata, quindi solo gli elementi rimasti nello stack mostrano che non è valido. - Fidarsi della lunghezza. Una lunghezza dispari è sempre non valida, ma una lunghezza pari non dimostra nulla:
(]e())(non sono validi. - Nell’approccio basato sulla rimozione, passare le parentesi a un’espressione regolare o a un pattern Lua senza eseguirne l’escape.
(e[hanno un significato in questi contesti; usa una sostituzione di testo semplice.
Domande frequenti3
Qual è la complessità temporale di Valid Parentheses?
La soluzione con lo stack richiede un tempo di O(n), poiché ogni carattere viene inserito o rimosso al massimo una volta. Nel caso peggiore, una stringa composta solo da parentesi di apertura, richiede uno spazio di O(n). Rimuovere ripetutamente le coppie corrispondenti richiede un tempo di O(n²), perché una stringa profondamente annidata perde solo una coppia per iterazione.
Perché si usa uno stack per le parentesi valide?
Le parentesi si annidano, quindi la parentesi aperta per ultima deve essere chiusa per prima. Uno stack mantiene quella parentesi in cima, dove puoi leggerla e rimuoverla in tempo costante, mantenendo l’intero controllo a O(n).
Una stringa vuota è una sequenza di parentesi valida?
Sì. Una stringa vuota non ha parentesi senza corrispondenza, quindi è bilanciata: lo stack rimane vuoto e il ciclo di rimozione non ha nulla da rimuovere. In questo problema s contiene sempre almeno un carattere.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def isValid(s):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomento
s = "[]{}()"Output atteso
true