Tutte le sfide
Media 0 risolte 0% di accettazione

Correttore ortografico

Elenca le parole di un testo che non si trovano nel dizionario, ignorando maiuscole, minuscole e punteggiatura.

Cosa imparerai

  • Caricare le parole in un insieme per ricerche veloci
  • Dividere il testo in parole con una regola sui caratteri
  • Riportare i risultati nell'ordine di prima comparsa senza duplicati

Problema

Un programma di videoscrittura sottolinea le parole che non conosce. Carica il dizionario in un insieme (set, cioè una tabella hash) così che ogni ricerca sia veloce, poi scorri il testo.

Una parola è una sequenza massimale di lettere inglesi (A-Z, a-z) e apostrofi; ogni altro carattere (spazi, cifre, punteggiatura) separa le parole. Le parole si confrontano senza distinguere tra maiuscole e minuscole, quindi The corrisponde alla voce del dizionario the.

Implementa spell_checker(dictionary, text).

Input

dictionary: le parole conosciute, scritte con maiuscole e minuscole in qualsiasi combinazione.

text: il testo da controllare.

Output

Restituisci le parole errate in minuscolo, nell'ordine in cui compaiono per la prima volta nel testo, ognuna una sola volta. Se tutte le parole sono conosciute, restituisci una lista vuota.

Vincoli

0 ≤ dimensione del dizionario ≤ 2 000

0 ≤ lunghezza di text ≤ 10 000

Esempi

Esempio 1
Input:
dictionary = ["the", "cat", "sat", "on", "mat"]
text = "The cat sat on teh mat, the cta!"

Output atteso:
expected = ["teh", "cta"]
Input:
std::vector<std::string> dictionary = {"the", "cat", "sat", "on", "mat"};
std::string text = "The cat sat on teh mat, the cta!";

Output atteso:
std::vector<std::string> expected = {"teh", "cta"};
Input:
string[] dictionary = new string[] {"the", "cat", "sat", "on", "mat"};
string text = "The cat sat on teh mat, the cta!";

Output atteso:
string[] expected = new string[] {"teh", "cta"};

Spiegazione

teh e cta non sono nel dizionario. Per le altre parole maiuscole e virgola non contano: ["teh", "cta"].

Esempio 2
Input:
dictionary = ["Don't", "stop"]
text = "don't STOP, dont stop dont"

Output atteso:
expected = ["dont"]
Input:
std::vector<std::string> dictionary = {"Don't", "stop"};
std::string text = "don't STOP, dont stop dont";

Output atteso:
std::vector<std::string> expected = {"dont"};
Input:
string[] dictionary = new string[] {"Don't", "stop"};
string text = "don't STOP, dont stop dont";

Output atteso:
string[] expected = new string[] {"dont"};

Spiegazione

don't mantiene l'apostrofo e viene trovata; dont è sconosciuta e compare una sola volta: ["dont"].

Come affrontarlo

Prova prima da solo, poi apri un suggerimento alla volta.

Suggerimento 1

Converti in minuscolo le parole del dizionario una volta sola, quando costruisci l'insieme.

Suggerimento 2

Costruisci la parola corrente carattere per carattere e chiudila quando incontri un carattere che non è né una lettera né un apostrofo.

Suggerimento 3

Tieni un secondo insieme con le parole già segnalate.

Complessità attesa

tempo O(D + T), spazio aggiuntivo O(D + T)

Riferimenti

Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.

La migliore soluzione superata di ogni programmatore. Le più veloci, leggere e meglio valutate stanno in alto.

Ancora nessuna soluzione superata. Risolvila e prendi il primo posto.

Impara dagli altri

Soluzioni della community

Nessuna soluzione pubblicata. Risolvi questa sfida per condividere la prima.