Todos os desafios
Médio 0 resolvidos 0% de aceitação

Corretor ortográfico

Liste as palavras de um texto que não estão no dicionário, ignorando maiúsculas, minúsculas e pontuação.

O que você vai aprender

  • Carregar palavras em um conjunto para consultas rápidas
  • Dividir um texto em palavras com uma regra de caracteres
  • Informar os resultados na ordem da primeira ocorrência, sem duplicatas

Problema

Ver original (inglês)

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

Exemplo 1
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"].

Exemplo 2
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.

A melhor solução aprovada de cada programador. As mais rápidas, leves e mais bem avaliadas ficam no topo.

Ainda não há soluções aprovadas. Resolva e fique com o primeiro lugar.

Aprenda com outros

Soluções da comunidade

Ainda não há soluções publicadas. Resolva este desafio para compartilhar a primeira.