Era +/- assim.
Eu consegui resolver tudo!
Não era bem os i´s e o´s da palavra. Sabendo à partida que se pode colocar e retirar caracteres dessa String da pilha através de push e pop, o push equivale por exemplo a um ‘i’ e um pop a um ‘o’. O objectivo é gerar todas as sequencias possiveis de push e pop dos caracteres da palavra.
Exemplo:
palavra: ola
Pode fazer push, push, push, pop, pop, pop / push, pop, push, pop, push, pop (…) para este caso tem 20 sequencias
Mas so algumas são válidas outras não. Isto é: ao fazer as operações na palavra é gerada outra palavra, segundo o meu primeiro exemplo -> alo, segundo exemplo -> “” pois faz pop e n esta la nada, so depois envia para a pilha os caracteres seguidos, e entao o resultado continua na mesma, como quando iniciado -> string vazia, resultado =""
No final comparamos a String encontrada, através das operações de push e pop (ou ‘i’ e ‘o’, como lhe queiramos chamar), à segunda palavra do Input. Se for igual devolve ou imprime a sequencia correspondente.
CÓDIGO
%%%%%
import java.io.IOException;
import java.util.Stack;
public class AbordagemA{
public static int tamanho_sequencia=0;
public static String input1="",input2="";
//método main
public static void main(String[] args){
do{
input1=readLine(100);
if(input1!=null){
input1.trim();
input2=readLine(100).trim();
tamanho_sequencia=input2.length();
System.out.println("[");
/** Start time of the current task */
long startTimeMillis=System.currentTimeMillis();
geraSequencias(tamanho_sequencia*2, 0, 0, “”);
long duration = System.currentTimeMillis() - startTimeMillis;
System.out.println("]");
System.out.println("Total Time: " + (duration) + “milisegundos”);
}
}while(input1!=null);
}
//método que gera as várias sequências
public static void geraSequencias(int num, int num_is, int num_os, String sequencia){
if(num==0){
if(sequencia.charAt(0)==‘i’)
compara(sequencia.substring(0,sequencia.length()-1));
}
else{
num–;
if(num_is<tamanho_sequencia)
geraSequencias(num, num_is+1, num_os, sequencia+"i ");
if(num_os<tamanho_sequencia)
geraSequencias(num, num_is, num_os+1, sequencia+"o ");
}
}
//método que devolve apenas as sequências correctas
public static void compara(String s){
Stack<String> pilha = new Stack<String>();
String resultado="";
int indice=0, var0=0, var1=1, l=s.length();
do{
if(s.charAt(indice)==‘i’){
pilha.push(input1.substring(var0,var1));
var0++;
var1++;
}else if(!pilha.empty()){
resultado+=pilha.pop();
}else break;
indice+=2;
}while(indice<l);
if(resultado.equals(input2))
System.out.println(s);
}
//método para leitura de uma linha
static String readLine (int maxLength){ //utility function to read from stdin
byte lin[] = new byte [maxLength];
int length = 0, car = -1;
try{
while (length < maxLength){
car = System.in.read();
if ((car < 0) || (car == ‘\n’)) break;
lin [length++] += car;
}
}catch (IOException e){
return (null);
}
if ((car < 0) && (length == 0)) return (null); //EOF
return (new String (lin, 0, length));
}
}
