24 de Março
Parênteses válidos
Como perceber que o fechamento precisa casar com a abertura mais recente e por que isso pede pilha.
Pilha Iniciante 15 min TypeScript
Dada uma string s contendo apenas os caracteres ()[]{}, retorne true se a string for valida.
Uma string e valida quando:
- cada abertura e fechada pelo mesmo tipo de parenteses
- cada abertura e fechada na ordem correta
Exemplo:
Input: s = "()[]{}"
Output: true
O que perceber antes de codar
- Não basta ter a mesma quantidade de abertura e fechamento.
- O fechamento atual precisa combinar com a abertura mais recente ainda pendente.
- Se aparecer um fechamento quando nada esta aberto, já falhou.
Erros comuns
- validar só pela contagem de cada simbolo
- procurar qualquer abertura compativel em vez da abertura mais recente
Passo 1 — Entender o que realmente precisa ser validado
Muita gente começa olhando só contagem.
Mas esse problema não e sobre quantidade. E sobre ordem e contexto.
([)] prova isso bem:
- abriu
( - abriu
[ - fechou
)antes de fechar[
A contagem bate. A estrutura não.
Passo 2 — Escrever uma versão inicial correta
Uma versão inicial possível e remover pares validos adjacentes até não dar mais:
export function isValid(s: string): boolean {
let current = s
let previous = ''
while (current.length !== previous.length) {
previous = current
current = current.replace('()', '').replace('[]', '').replace('{}', '')
}
return current.length === 0
}
Funciona, mas e ineficiente. Cada passada cria novas strings e repete trabalho.
Passo 3 — Reformular a pergunta
Quando chega um fechamento, o que você realmente precisa saber?
Não e "existe alguma abertura desse tipo?".
E:
a ultima abertura que ficou pendente combina com este fechamento?
Isso já aponta para uma estrutura LIFO.
Passo 4 — Guardar o contexto aberto
Pilha faz exatamente isso:
- quando abre, empilha
- quando fecha, desempilha
- se o tipo não bater, falhou
- no final, a pilha precisa estar vazia
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function isValid(s: string): boolean {
// sua solução aqui
return false
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n)
Espaço: O(n)
Solução 1 — Remover pares O(n²)
Uma versão inicial simples e ir removendo pares validos visíveis.
export function isValid(s: string): boolean {
let current = s
let previous = ''
while (current.length !== previous.length) {
previous = current
current = current.replace('()', '').replace('[]', '').replace('{}', '')
}
return current.length === 0
}Funciona. Mas fica ruim porque você reprocessa a string várias vezes.
Solução 2 — Pilha O(n)
Se o fechamento precisa casar com a abertura mais recente, use pilha.
export function isValid(s: string): boolean {
const pairs: Record<string, string> = {
')': '(',
']': '[',
'}': '{',
}
const stack: string[] = []
for (const char of s) {
if (char in pairs) {
if (stack.pop() !== pairs[char]) {
return false
}
continue
}
stack.push(char)
}
return stack.length === 0
}Agora a estrutura do problema bate com a estrutura de dados.
O que dizer na entrevista
Uma explicação curta e boa seria:
O problema não e só de contagem. O fechamento precisa combinar com a abertura mais recente ainda aberta. Por isso
pilhaencaixa bem: empilho aberturas, desempilho ao fechar, e valido o tipo emO(n).
Isso mostra que você:
- identificou a regra real do problema
- justificou a estrutura de dados
- explicou a solução em termos de contexto, não de truque
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- rastrear contexto aberto
- validar ordem de fechamento
- desfazer o ultimo estado primeiro
- processar estruturas aninhadas
O ponto não e decorar
pilha.
O ponto e perceber quando o problema pede “o ultimo que entrou e o primeiro que precisa sair”.