Riorganizzando le corde in modo che la distanza di Hamming tra di loro sia 1

Question

Questa è una domanda da Codefights.com:

Data una serie di stringhe di uguale lunghezza, controlla se è possibile riorganizzare le corde in modo tale che dopo il riarrangiamento le corde in posizioni consecutive differiscono esattamente di un carattere.

Esempio

• Per inputArray = ["aba", "bbb", "bab"], l'output dovrebbe essere stringsRearrangement(inputArray) = false; Tutti i riarrangiamenti non soddisfano la condizione di descrizione. (sic)

• Per inputArray = ["ab", "bb", "aa"], l'output dovrebbe essere stringsRearrangement(inputArray) = true. Le stringhe possono essere riorganizzate nel modo seguente: "aa", "ab", "bb".

Ho trovato un algoritmo a tempo esponenziale, ma esiste un algoritmo a tempo polinomiale? Questo problema è NP-completo?

So che un problema strettamente correlato, il Hamming Salesman Problem (HTSP), è NP-completo e questo problema è certamente riducibile a HTSP, ma non so se HTSP è riducibile a questo.