Valid Parentheses

Q: Qual é a complexidade de tempo de Valid Parentheses?

A solução com pilha é executada em tempo O(n) , pois cada caractere é empilhado ou desempilhado no máximo uma vez. Ela usa espaço O(n) no pior caso, quando a string contém apenas caracteres de abertura. Remover pares correspondentes repetidamente leva tempo O(n²) , pois uma string profundamente aninhada perde apenas um par por rodada.

FácilPilha

+10

Você recebe uma string s composta apenas pelos caracteres de colchetes (, ), [, ], { e }. Retorne true quando os colchetes estiverem balanceados: cada colchete de fechamento fecha o colchete mais recente que ainda está aberto, ambos são do mesmo tipo e nenhum permanece aberto no final. Caso contrário, retorne false.

Função

isValid(s: string) → boolean

sstring: a sequência de colchetes a verificar
Retornaboolean: se os colchetes estão balanceados

Restrições

1 ≤ s.length ≤ 10⁴
s contém apenas os caracteres (, ), [, ], { e }.

Exemplos

Entrada: s = "[]{}()"
Saída: true
Explicação: Três pares ficam lado a lado, e cada um se fecha logo depois de ser aberto.

Entrada: s = "{(})"
Saída: false
Explicação: O } chega enquanto o ( aberto depois dele ainda está aberto, então fecha o tipo errado de colchete.

Para ir além

Se a string contivesse apenas parênteses, você poderia verificá-la com um único contador em vez de uma pilha, usando espaço extra O(1)?

Solução

Contar os colchetes não é suficiente: {(}) tem um de cada tipo de abertura e fechamento e ainda assim está incorreto, porque a ordem importa. Uma pilha mantém os colchetes que ainda estão abertos na ordem em que foram abertos, então uma única passagem com uma pilha determina se a string inteira está correta.

Remova repetidamente os pares correspondentes

Correta, mas não termina nos maiores testes

Intuição

Toda string balanceada tem um par mais interno sem nada entre seus colchetes, como o () dentro de {[()]}. Excluir um par adjacente correspondente nunca altera se uma string está balanceada. Portanto, repita as exclusões até que uma rodada não remova nada: uma string balanceada fica vazia, e uma não balanceada fica travada com caracteres restantes, como {(}) desde o início.

Cada rodada percorre a string inteira e cria uma cópia nova, e uma string aninhada como (((...))) perde um par por rodada. Isso significa até n/2 rodadas de trabalho O(n), O(n²) no total.

Algoritmo

Remova todos os (), [] e {} da string.
Se essa rodada não remover nada, pare.
Caso contrário, repita com a string mais curta.
Retorne true se a string acabar vazia e false se restar algum colchete.

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 == ""

Uma única passagem com uma pilha

Intuição

Um colchete de fechamento deve fechar o colchete aberto mais recentemente que ainda esteja aberto. O último colchete aberto é o primeiro a ser fechado, e essa ordem de último a entrar, primeiro a sair é exatamente o que uma pilha mantém.

Empilhe o delimitador de fechamento que cada delimitador de abertura aguarda. Em seguida, um delimitador de fechamento deve ser igual ao topo da pilha. Uma pilha vazia significa que não há nada para fechar; um topo diferente significa que ele fecha o tipo errado, como acontece com } em {(}) enquanto ) está no topo. No final, tudo o que restar na pilha, como em ((, foi aberto e nunca fechado. Cada caractere é empilhado ou desempilhado uma vez: tempo O(n) e, no máximo, n entradas na pilha.

Algoritmo

Crie uma pilha vazia.
Para um colchete de abertura, empilhe seu correspondente de fechamento.
Para um colchete de fechamento, retorne false se a pilha estiver vazia ou se o topo dela for um caractere diferente; caso contrário, desempilhe.
Após o último caractere, retorne true somente se a pilha estiver vazia.

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

Armadilhas e casos extremos

Contar cada tipo de colchete. {(}) tem quantidades correspondentes e ainda é inválido, e )( falha apenas pela ordem.
Remover de uma pilha vazia. Uma string que começa com um delimitador de fechamento, como } ou )]}, deve retornar false em vez de causar um erro.
Ignorar a verificação final. (([{ nunca encontra um delimitador de fechamento incorreto, então apenas o que resta na pilha mostra que ela é inválida.
Confiar no comprimento. Um comprimento ímpar é sempre inválido, mas um comprimento par não prova nada: (] e ())( são ambos inválidos.
Na abordagem de remoção, passar delimitadores para uma expressão regular ou um padrão Lua sem escapá-los. ( e [ têm um significado nesses padrões; use uma substituição de texto simples.

Perguntas frequentes3

Qual é a complexidade de tempo de Valid Parentheses?

A solução com pilha é executada em tempo O(n), pois cada caractere é empilhado ou desempilhado no máximo uma vez. Ela usa espaço O(n) no pior caso, quando a string contém apenas caracteres de abertura. Remover pares correspondentes repetidamente leva tempo O(n²), pois uma string profundamente aninhada perde apenas um par por rodada.

Por que uma pilha é usada para parênteses válidos?

Os colchetes podem ser aninhados, então o colchete aberto por último deve ser fechado primeiro. Uma pilha mantém esse colchete no topo, onde você pode consultá-lo e removê-lo em tempo constante, o que mantém toda a verificação em O(n).

Uma string vazia é uma sequência válida de parênteses?

Sim. Uma string vazia não tem nenhum delimitador sem correspondência, então está balanceada: a pilha permanece vazia, e o loop de remoção não tem nada para remover. Neste problema, s sempre tem pelo menos um caractere.

def isValid(s):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

s = "[]{}()"

Saída Esperada

true