Considere uma pilha que armazene caracteres. Faça uma função para determinar se uma string é da forma XY, onde
é uma cadeia formada por caracteres arbitrários e
é o reverso de
. Por exemplo, se
, então
. Considere que
e y são duas strings distintas.
Passo 1
A ideia aqui é usar uma pilha (estrutura LIFO) para guardar a primeira metade da string e depois comparar, na ordem inversa, com a segunda metade. O conteúdo envolve operações de pilha (push e pop) e manipulação de índices de string.
Passo 2
Primeiro, calculamos o tamanho da string
e verificamos se
é par. Se
for ímpar, não dá para dividir em duas metades iguais, então já retornamos falso.
Em seguida, definimos . Fazemos um laço de
até
e damos
de
na pilha. Isso empilha exatamente os caracteres de
.
Em seguida, definimos
Passo 3
Agora fazemos outro laço de
até
. A cada iteração, verificamos se a pilha está vazia (se estiver, retornamos falso por segurança), então damos
e comparamos com
. Se eles forem diferentes, retornamos falso imediatamente.
Passo 4
Se conseguirmos percorrer toda a segunda metade sem mismatches e a pilha esvaziar corretamente, concluímos que a segunda metade é o reverso da primeira e retornamos verdadeiro.
Resposta
Função isReverso(S):
- n ← |S|
- Se n mod 2 ≠ 0 então retorne falso
- m ← n/2
- Pilha P vazia
- Para i de 0 até m-1 faça
• P.push(S[i]) - Para i de m até n-1 faça
• Se P estiver vazia então retorne falso
• c ← P.pop()
• Se c ≠ S[i] então retorne falso - Retorne verdadeiro