Palavras

Esse problema caiu no simulado realizado no IC no em Outubro de 2014.

Trata-se de um problema também resolvido com backtracking, mas nesse caso você precisa gerenciar dois arrays ao mesmo tempo e compará-los a cada passo do backtracking.

Uma das dificuldades era descobrir as condições de parada. No problema ele diz que as palavras não excedem 40 caracteres. Não fica muito claro se ele se refere as palavras de cada conjunto ou também à palavra gerada pela concatenação.

Mas nesse caso, a interpretação correta é que o limite de 40 caracteres se aplica a qualquer palavra, inclusive a palavra da concatenação. Sendo assim, temos duas condições de parada, uma quando encontramos uma concatenação igual e outra quando ultrapassamos 40 caracteres de tamanho.

Depois que você resolver esse problema, cadastramos um outro problema no The Huxley, chamado "palavras 2" que retira essa condição de parada dos 40 caracteres. Fica bem mais difícil, mas vamos por partes e voltar ao nosso problema.

A ideia é a seguinte.

Sejam os conjuntos de palavras s0 e s1.

Nesse caso, tanto s0 quanto s1 podem ser vector de strings.Então, resolvi criar um array global de vector com dois elementos:

typedef vector<string> vs;

vs s[2];

Criamos duas strings globais para representar as concatenações de s0 e s1: c0 e c1. Inicialmente essas strings estão vazias.

string c[2];

Não faz muita diferença escolher s0 ou s1 para começar. Então escolhemos s0.

void backtrack(int word_index)

Perceba que o único parâmetro que passamos para o backtrack é quem vamos utilizar, se o s0 ou s1. Ou seja, 0 significa que iremos utilizar o s[0] e 1 o s[1].

Chamamos a função backtrack com s0:

void backtrack(0)

A condição de parada do backtrack ocorre em dois casos:

1- Quando c[0] for igual a c[1], ou seja, quando as duas strings geradas forem iguais. Nesse caso, você encontrou uma solução.

2- Quando c[0] ou c[1] ultrapassar 40 caracteres.

A função find_candidates irá então encontrar os candidatos para word_index. Ela irá verificar quais são as palavras de s[word_index] que podem ser candidatas. Para isso, ela verifica se o resultado concatenação da palavra com c[word_index] é prefixo da outra palavra. Por exemplo, se word_index for 0, então tivemos que verificar se c[0] é prefixo de c[1] e vice-versa.

Por exemplo, se estamos escolhendo usar uma palavra do s[0], então iremos concatenar essa palavra em c[0] e verificar se c[0] é prefixo de c[1] ou c[1] é prefixo de c[0]. Quando c[0] ou c[1] é vazio, a palavra escolhida sempre será um candidato.

A minha assinatura de find_candidates ficou:

void find_candidates(int word_index, vs *candidates)

Suponha s[0] = { "010", "11"} e s[1]= {"0", "101" } e inicialmente: c[0] = "" e c[1]=""

Na primeira chamada de find_candidates, passando como parâmetro o 0, retornaríamos como candidatos todos os elementos do conjunto, ou seja, os candidatos seriam "010" e "11"

Como estamos pegando os candidatos do conjunto 0, então iremos concatenar no c[0]. Do ponto de vista lógico, faremos:

vs candidates;

find_candidates(word_index, &candidates)

Para cada candidato in candidates:

valor_antigo = c[word_index] // guarda o valor antigo

c[word_index] += candidato

backtrack( ? )

c[word_index] = valor_antigo // restaura o valor antigo

fim_para

Conforme você deve ter percebido no pseudocódigo acima, precisamos definir de qual conjunto escolheremos a próxima palavra. Perceba que na primeira vez, você terá adicionado um valor em c[0] e c[1] continuará vazio. Logo, parece intuitivo tentar adicionar na próxima vez uma palavra em c[1]. Ou seja, iremos sempre escolher o lado em que o c[i] tiver o menor tamanho de string.

Nesse caso chamaremos backtrack(1).

É importante ver o que vai acontecer agora na função find_candidates. Dessa vez, tentaremos escolher um elemento de s[1]. O primeiro a ser tentado é 0 e a pergunta que será feita é se 0 é prefixo de c[0] ou se c[0] é prefixo desse c[1]. Lembre-se que c[0] atualmente está com o valor :"010". Nesse caso "0" é prefixo de "010", portanto será candidato. O próximo elemento é o "101". "101" não é prefixo de "010" e nem vice-versa, logo, "101" não é candidato. A função find_candidates retornará nesse caso apenas um único elemento.

Basicamente é isso.

Lembre-se dos passos do backtracking: backtracking