Problème
Un traitement de texte souligne les mots qu'il ne connaît pas. Chargez le dictionnaire dans un ensemble (une table de hachage) pour que chaque recherche soit rapide, puis parcourez le texte.
Un mot est une suite maximale de lettres latines (A-Z, a-z) et d'apostrophes ; tout autre caractère (espaces, chiffres, ponctuation) sépare les mots. Les mots sont comparés sans tenir compte de la casse : The correspond à l'entrée the du dictionnaire.
Implémentez spell_checker(dictionary, text).
Entrée
dictionary : les mots connus. Ils peuvent être écrits avec n'importe quelle casse.
text : le texte à vérifier.
Sortie
Renvoyez les mots mal orthographiés en minuscules, dans l'ordre de leur première apparition dans le texte, chacun une seule fois. Renvoyez une liste vide si tous les mots sont connus.
Contraintes
0 ≤ taille du dictionnaire ≤ 2 000
0 ≤ longueur de text ≤ 10 000
Exemples
Entrée :
dictionary = ["the", "cat", "sat", "on", "mat"]
text = "The cat sat on teh mat, the cta!"
Sortie attendue :
expected = ["teh", "cta"]
Entrée :
std::vector<std::string> dictionary = {"the", "cat", "sat", "on", "mat"};
std::string text = "The cat sat on teh mat, the cta!";
Sortie attendue :
std::vector<std::string> expected = {"teh", "cta"};
Entrée :
string[] dictionary = new string[] {"the", "cat", "sat", "on", "mat"};
string text = "The cat sat on teh mat, the cta!";
Sortie attendue :
string[] expected = new string[] {"teh", "cta"};
Explication
teh et cta ne sont pas dans le dictionnaire. Pour les autres mots, la casse et la virgule n'ont pas d'importance : ["teh", "cta"].
Entrée :
dictionary = ["Don't", "stop"]
text = "don't STOP, dont stop dont"
Sortie attendue :
expected = ["dont"]
Entrée :
std::vector<std::string> dictionary = {"Don't", "stop"};
std::string text = "don't STOP, dont stop dont";
Sortie attendue :
std::vector<std::string> expected = {"dont"};
Entrée :
string[] dictionary = new string[] {"Don't", "stop"};
string text = "don't STOP, dont stop dont";
Sortie attendue :
string[] expected = new string[] {"dont"};
Explication
don't garde son apostrophe et figure dans le dictionnaire ; dont est inconnu et n'est listé qu'une fois : ["dont"].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Mettez les mots du dictionnaire en minuscules une seule fois, en construisant l'ensemble.
Indice 2
Construisez le mot courant caractère par caractère et terminez-le dès que vous rencontrez un caractère qui n'est ni une lettre ni une apostrophe.
Indice 3
Gardez un second ensemble avec les mots déjà signalés.
Complexité attendue
temps O(D + T), espace supplémentaire O(D + T)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.