Problema
Un procesador de texto subraya las palabras que no conoce. Carga el diccionario en un conjunto (una tabla hash) para que cada búsqueda sea rápida y luego recorre el texto.
Una palabra es la secuencia más larga posible de letras del alfabeto inglés (A-Z, a-z) y apóstrofos; cualquier otro carácter (espacios, dígitos, signos de puntuación) separa palabras. Las palabras se comparan sin distinguir mayúsculas de minúsculas, así que The coincide con la entrada the del diccionario.
Implementa spell_checker(dictionary, text).
Entrada
dictionary: las palabras conocidas. Pueden estar en mayúsculas o minúsculas.
text: el texto que hay que revisar.
Salida
Devuelve las palabras mal escritas en minúsculas, en el orden en que aparecen por primera vez en el texto y sin repetir ninguna. Devuelve una lista vacía si todas las palabras son conocidas.
Restricciones
0 ≤ tamaño del diccionario ≤ 2,000
0 ≤ longitud de text ≤ 10,000
Ejemplos
Entrada:
dictionary = ["the", "cat", "sat", "on", "mat"]
text = "The cat sat on teh mat, the cta!"
Salida 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!";
Salida 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!";
Salida esperada:
string[] expected = new string[] {"teh", "cta"};
Explicación
teh y cta no están en el diccionario. En las demás palabras no importan las mayúsculas ni la coma: ["teh", "cta"].
Entrada:
dictionary = ["Don't", "stop"]
text = "don't STOP, dont stop dont"
Salida esperada:
expected = ["dont"]
Entrada:
std::vector<std::string> dictionary = {"Don't", "stop"};
std::string text = "don't STOP, dont stop dont";
Salida esperada:
std::vector<std::string> expected = {"dont"};
Entrada:
string[] dictionary = new string[] {"Don't", "stop"};
string text = "don't STOP, dont stop dont";
Salida esperada:
string[] expected = new string[] {"dont"};
Explicación
don't conserva su apóstrofo y está en el diccionario; dont es desconocida y aparece una sola vez en la lista: ["dont"].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Pasa a minúsculas las palabras del diccionario una sola vez, al construir el conjunto.
Pista 2
Construye la palabra actual carácter por carácter y termínala cuando encuentres algo que no sea letra ni apóstrofo.
Pista 3
Lleva un segundo conjunto con las palabras que ya reportaste.
Complejidad esperada
tiempo O(D + T), espacio extra O(D + T)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.