Eliminar pares adjacentes
A missão
Problema
Dado um texto, apague repetidamente quaisquer dois caracteres vizinhos que sejam idênticos. Apagar um par aproxima os caracteres ao redor, o que pode criar um novo par vizinho para apagar. Continue até não sobrar nenhum par assim e retorne o que restou.
Exemplos
Input: text = "abbaca"
Output: "ca"
Por quê: remover bb deixa aaca, e remover aa deixa ca
Input: text = "azxxzy"
Output: "ay"
Por quê: apagar xx cria zz, que também se apaga
Input: text = "aa"
Output: ""
Por quê: edge case: tudo se cancela e não sobra nada
Dicas
0 / 3
Varrer o texto inteiro de novo depois de cada remoção é correto, mas lento. Repare que uma remoção só pode afetar os caracteres imediatamente ao redor do buraco que ela deixa.
Construa o resultado da esquerda para a direita e fique de olho no último caractere dele. Uma estrutura cujas únicas operações baratas são adicionar no fim e remover do fim se encaixa nisso perfeitamente.
Empilhe (push) os caracteres um de cada vez. Antes de empilhar, compare o caractere que chega com o do topo: se forem iguais, desempilhe (pop) em vez de empilhar, o que faz o cancelamento e já expõe o próximo candidato logo abaixo. No final, junte o que sobrou na pilha.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(n)
Solução
Uma pilha guarda a parte da resposta construída até agora, e o topo dela é sempre o caractere ao lado do qual um recém-chegado ficaria. Por isso, uma coincidência se cancela desempilhando em vez de empilhar, o que também expõe o caractere de baixo como o novo vizinho; assim, cadeias de cancelamentos acontecem automaticamente, sem varrer tudo de novo. Cada caractere é empilhado e desempilhado no máximo uma vez. O tempo é O(n) e o espaço é O(n) para a pilha.
def collapse_pairs(text):
stack = []
for ch in text:
if stack and stack[-1] == ch:
stack.pop() # the pair annihilates, exposing the one below
else:
stack.append(ch)
return "".join(stack)
print(collapse_pairs("abbaca")) # -> ca
print(collapse_pairs("azxxzy")) # -> ay
print(collapse_pairs("aa")) # ->Travou na ideia, e não no código? Valid Parentheses explica isso.