Tous les défis
Moyen 0 résolus 0 % de réussite

Correcteur orthographique

Listez les mots d'un texte absents d'un dictionnaire, sans tenir compte de la casse ni de la ponctuation.

Ce que vous allez apprendre

  • Charger des mots dans un ensemble pour des recherches rapides
  • Découper un texte en mots selon une règle sur les caractères
  • Donner les résultats dans l'ordre de première apparition, sans doublons

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

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

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

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.