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