Talvez guardando as palavras da lista e suas inversões dentro de uma estrutura de dados chamada TRIE (nao é TREE rsrs) você consiga alcançar a solução do seu problema ate com um tempo de busca interessante, caso funcione.

Tente e poste o codigo da solução aqui pra vermos.