Então, meu mano, eu faria assim:
- 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.
- 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.