Problema
Um editor de texto sublinha as palavras que não conhece. Carregue o dicionário em um conjunto (uma tabela hash) para que cada consulta seja rápida e, depois, percorra o texto.
Uma palavra é a maior sequência possível de letras do alfabeto inglês (A-Z, a-z) e apóstrofos; qualquer outro caractere (espaços, dígitos, pontuação) separa palavras. As palavras são comparadas sem diferenciar maiúsculas de minúsculas, então The corresponde à entrada the do dicionário.
Implemente spell_checker(dictionary, text).
Entrada
dictionary: as palavras conhecidas. Podem estar em maiúsculas ou minúsculas.
text: o texto a verificar.
Saída
Retorne as palavras com erro em minúsculas, na ordem em que aparecem pela primeira vez no texto, cada uma listada uma única vez. Retorne uma lista vazia quando todas as palavras forem conhecidas.
Restrições
0 ≤ tamanho do dicionário ≤ 2000
0 ≤ tamanho de text ≤ 10 000
Exemplos
Entrada:
dictionary = ["the", "cat", "sat", "on", "mat"]
text = "The cat sat on teh mat, the cta!"
Saída esperada:
expected = ["teh", "cta"]
Entrada:
std::vector<std::string> dictionary = {"the", "cat", "sat", "on", "mat"};
std::string text = "The cat sat on teh mat, the cta!";
Saída esperada:
std::vector<std::string> expected = {"teh", "cta"};
Entrada:
string[] dictionary = new string[] {"the", "cat", "sat", "on", "mat"};
string text = "The cat sat on teh mat, the cta!";
Saída esperada:
string[] expected = new string[] {"teh", "cta"};
Explicação
teh e cta não estão no dicionário. Nas outras palavras, maiúsculas e a vírgula não fazem diferença: ["teh", "cta"].
Entrada:
dictionary = ["Don't", "stop"]
text = "don't STOP, dont stop dont"
Saída esperada:
expected = ["dont"]
Entrada:
std::vector<std::string> dictionary = {"Don't", "stop"};
std::string text = "don't STOP, dont stop dont";
Saída esperada:
std::vector<std::string> expected = {"dont"};
Entrada:
string[] dictionary = new string[] {"Don't", "stop"};
string text = "don't STOP, dont stop dont";
Saída esperada:
string[] expected = new string[] {"dont"};
Explicação
don't mantém o apóstrofo e é encontrada; dont é desconhecida e aparece uma vez: ["dont"].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Converta as palavras do dicionário para minúsculas uma única vez, ao montar o conjunto.
Dica 2
Monte a palavra atual caractere por caractere e encerre-a quando encontrar algo que não seja letra nem apóstrofo.
Dica 3
Mantenha um segundo conjunto com as palavras já informadas.
Complexidade esperada
tempo O(D + T), espaço extra O(D + T)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.