Então, meu mano, eu faria assim:

1. Pegaria a entrada do usuário e removeria números e outros caracteres que não fossem letras, e deixaria todas as letras minúsculas.
2. Criaria uma função que gera uma permutação e verifica se essa nova palavra combina com alguma palavra do array.

Dá uma pesquisada sobre permutações, é um tema interessante e bate com o que você está tentando criar.