Diseño de un sistema que detectaría errores tipográficos y sugerencias

Question

Esto se preguntó en una entrevista.

Creo que la respuesta se puede hacer construyendo un trie de todas las palabras válidas y luego se pueden hacer sugerencias en base a una posible ruta válida que de otro modo se dio como incorrecta.

Digamos que si los usuarios tipos APFLE, y el sistema detectaría que después de AP, una posible ruta válida era la aplicación, lo que satisfaría a Apple.

¿Hay alguna mejor solución que esta? Quizás el implementado por los correctores de ortografía.