Todos los desafíos
Intermedio 0 resueltos 0% de aceptación

Corrector ortográfico

Lista las palabras de un texto que no están en el diccionario, sin distinguir mayúsculas ni signos de puntuación.

Lo que aprenderás

  • Cargar palabras en un conjunto para búsquedas rápidas
  • Dividir un texto en palabras con una regla de caracteres
  • Informar los resultados en orden de aparición y sin duplicados

Problema

Ver original (inglés)

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

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

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

Clasificación

Clasificación completa

La mejor solución aprobada de cada programador. Las más rápidas, ligeras y mejor valoradas van primero.

Aún no hay soluciones aprobadas. Resuélvelo y quédate el primer puesto.

Aprende de otros

Soluciones de la comunidad

Aún no hay soluciones publicadas. Resuelve este reto para compartir la primera.