Nesse problema, o objetivo é decodificar uma lista de frases usando as palavras do dicionário.
Por exemplo, para a entrada:
6
and
dick
jane
puff
spot
yertle
bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn
xxxx yyy zzzz www yyyy aaa bbbb ccc dddddd
A saída deve ser:
dick and jane and puff and spot and yertle
**** *** **** *** **** *** **** *** ******
Quando não é possível decodificar, devemos substituir cada letra por um asterisco.
Cada linha possui uma codificação independente da outra. Além disso, uma leitura atenta da descrição revela outras características importantes:
- cada palavra do dicionário tem no máximo 16 letras;
- o dicionário possui no máximo 1000 palavras;
- ele não define um número máximo de frases que serão usadas na entrada, ou seja, podem ser muitas frases.
A ideia geral que usei para resolver foi a seguinte:
Para cada palavra da frase dada, eu procuro no dicionário se existe uma palavra que torne possível a substituição, letra por letra. Se por possível, eu pego a segunda palavra e vou construindo.
Como o número de palavras no dicionário pode chegar a 1000 e cada frase pode fazer muitas buscas nesse dicionário, achei melhor organizar a busca para evitar uma busca O(n) no dicionário.
A primeira observação é que só faz sentido tentar realizar uma substituição se a palavra a ser decodificada possuir o mesmo número de letras da palavra do dicionário.
Usando essa informação, eu leio todas as palavras do dicionário em um array e ordeno de acordo com o tamanho, colocando as menores palavras na frente.
Aí eu guardo em um array auxiliar onde está a primeira palavra com um determinado tamanho. Por exemplo, para a entrada:
dick
abcdef
jane
and
yertle
spot
meu dicionário ficaria:
[0]=and
[1]=dick
[2]=jane
[3]=spot
[4]=yertle
[5]=abcdefgh
Já o meu array auxiliar ficaria:
[0]=-1
[1]=-1
[2]=-1
[3]=0
[4]=1
[5]=-1
[6]=4
[7]=-1
[8]=5
[9]=-1
[10]=-1
[11]=-1
[12]=-1
[13]=-1
[14]=-1
[15]=-1
[16]=-1
Perceba que o dicionário está ordenado por tamanho. O array auxiliar guarda que a primeira palavra com 3 letras está no índice 0 do array de dicionários, a primeira palavra com 4 letras está no índice 1, a primeira palavra com 6 letras está no índice 4 e a primeira com 8 letras está no índice 5.
Isso foi possível porque as palavras do dicionário possuem no máximo 16 letras.
Agora, com esse índice, dada uma palavra que eu quero decodificar, eu posso ir direto na posição do
dicionário. Por exemplo, se eu estiver tentando decodificar a string "wzqr", eu vejo que ela possui quatro letras, então eu vou no meu array auxiliar e vejo que a primeira palavra com 4 letras está na posição 1 do dicionário. Essa palavra seria dick.
Agora chegou a hora de definir como iremos testar as possibilidades de decodificação. A ideia (bem simplificada aqui) é receber uma frase, separar a primeira palavra e tentar decodificar somente a primeira palavra. Se der certo, você tenta recursivamente com o resto da frase. Se não der certo, você tenta com outra palavra. Acharemos a resposta quando a frase restante for vazia, ou seja, conseguimos decodificar todas as palavras. A cada decodificação, temos que guardar quais foram os mapeamentos de letra que utilizamos. Além disso, o problema diz que o mapeamento é de 1 pra 1, ou seja, se você mapear, por exemplo, b-->c, não pode existir um mapeamento de qualquer outra letra para c. Apenas b poderia ser mapeado para c.
Com isso em mente, tome cuidado para cada vez que a sua busca falhar por um determinado caminho, você restaure os mapeamentos para o ponto de antes da tentativa.
decode_sentence(sentence, decoded_sentence)
{
if (sentence is empty)
{
// sucesso
return decoded_sentence
}
saved_sentence = decoded_sentence // guarda
word = first_word(sentence) // separa a primeira palavra
while ( not tried every word )
{
decoded_word = decode_word(word) // tenta decodificar a palavra
if (decoded_word)
{
// se der certo, decodifica o resto da frase
decoded_sentence = decoded_word + decode_sentence(remaining)
}
if (! sucess)
{
decoded_sentence = saved_sentence
}
// tenta a próxima palavra
word = next_word()
}
}
Quando terminar e conseguir CORRETO lá no Huxley (crypt kicker), que tal tentar com o arquivo abaixo. Lembre-se de usar o diff para comparar a sua resposta.
Arquivo grande para teste (seu tempo de execução deve ser inferior a 2 segundos):
Entrada: https://raw.githubusercontent.com/r0drigopaes/pa/master/crypt.in
Saída: https://raw.githubusercontent.com/r0drigopaes/pa/master/crypt.out