Pular para o conteúdo

Valid Parentheses

Aula 2 de 9 · 5 min

Valid Parentheses

Passo 1 de 14

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.

  1. Retorne True só se a pilha terminar vazia
  2. Comece com uma pilha vazia
  3. Empilhe todo símbolo de abertura
  4. Em um símbolo de fechamento, desempilhe o topo e compare os pares

Mini quiz

1 / 3

O que uma pilha vazia no fim da varredura diz a você?