Valid Parentheses
Passo 1 de 14
vereditovarrendo
varrendo "{[()]}"
{
[
(
)
]
}
(
]
pilhavazia
{
[
(
(
Todo símbolo de abertura vai para a pilha. Um de fechamento precisa responder ao aberto mais recentemente.
A ideia
Empilhe (push) todo símbolo de abertura. Quando aparece um de fechamento, ele precisa casar com o do topo — o aberto mais recentemente. Qualquer outra coisa significa que a string está quebrada. Uma passada, O(n), e uma entrada válida termina com a pilha vazia.
Exemplo do mundo real
Um editor de código conferindo o seu markup enquanto você digita. Feche um </section> com um <div> ainda aberto e a linha acende na hora, porque a tag que você fecha precisa ser a última que você abriu, não qualquer tag que ainda esteja pendente.
O código
Sua vez
Coloque os passos em ordem.
- Retorne True só se a pilha terminar vazia
- Comece com uma pilha vazia
- Empilhe todo símbolo de abertura
- Em um símbolo de fechamento, desempilhe o topo e compare os pares
Mini quiz
1 / 3