Anagramas a partir de pilhas

URL

https://www.thehuxley.com/problem/411

Comentários

Neste problema, a gente recebe uma entrada e tem que ver se a partir das operações de pilha, conseguimos gerar a saída.

Por exemplo, se recebermos a entrada "ab", a gente poderia ter as seguintes operações:

i i o o

i o i o

Existem vários desafios nesse problema, mas os principais são:

1- Como simular as várias operações de pilha considerando somente as operações válidas?

2- Como fazer isso de forma eficiente, uma vez que teremos que explorar todas as possibilidades?

Não iremos conseguir fugir de ter que avaliar todas as possibilidades. Porém, podemos verificar se a operação é válida ou se geraria a saída esperada antes de continuar.

Imagine que você vai explorar todas as possibilidades de operação. Como você só tem 2 operações possíveis: push ou pop, a cada momento, temos dois caminhos de decisão. Um árvore binária representaria bem essa situação.

Nesse cenário, se você tiver uma palavra com 2 letras, seriam necessárias pelos menos 4 operações para gerar a saída: push, push, pop, pop. Ou seja, para uma palavra de tamanho n, teríamos uma árvore de altura 2*n. Como a quantidade de nós folha é dado por 2^altura, teríamos 16 possibilidades diferentes. Isso, para uma entrada de tamanho 2. Para uma entrada de tamanho 100, esse número já iria para 2^200, que é igual a 1,606938044×10⁶⁰.

Entretanto, basta olhar para esta árvore que veremos que muitas das opções acima não são válidas. Por exemplo, o primeiro ramo a direita começa com um a operação 'o' (pop) , mas só que nesse momento a pilha estava vazia e logo, o pop não é possível.

Essa é a estratégia que usaremos nesse problema. Vamos fazer uma busca em uma árvore, porém vamos podar a árvore para evitar expandir ramos desnecessários.

Optei por fazer uma busca em profundidade, mas uma busca em largura também resolveria o problema. Em termos de eficiência, não mudaria, pois teremos que explorar todos os caminhos viáveis do mesmo jeito.

Eu sempre tento primeiro fazer um push e então chamo recursivamente a função que percorre a árvore. Mas quando a entrada está vazia, eu executo um pop.

As podas que fiz na árvore se basearam na operação de pop. Antes de fazer o pop, verifiquei se a substring resultante das operações de pop até aquele momento estava igual a palavra que a gente estava querendo gerar. Se elas fossem diferentes, então não adiantava expandir.

A minha função que percorre a árvore tem a seguinte assinatura:

void find_path(string input, string output, string str_stack, string path, int depth)

O primeiro parâmetro armazena como está a entrada até aquele momento. O segundo guarda o resultado das operações de pop. O str_stack representa a pilha de caracteres. Nesse caso, optei por usar uma string mesmo ao invés de usar a classe stack. O path é uma string que guarda as operações realizadas até aquele momento, por exemplo: "iiioo". Finalmente o depth guarda em que altura a árvore já está.

A imagem abaixo mostra a árvore de execução dessa função, quando chamada recursivamente.