Rearranging strings so that the Hamming distance between them is 1
-
04-11-2019 - |
Question
This is a question from CodeFights.com:
Given an array of equal-length strings, check if it is possible to rearrange the strings in such a way that after the rearrangement the strings at consecutive positions would differ by exactly one character.
Example
For
inputArray = ["aba", "bbb", "bab"]
, the output should bestringsRearrangement(inputArray) = false
; All rearrangements don't satisfy the description condition. (sic)For
inputArray = ["ab", "bb", "aa"]
, the output should bestringsRearrangement(inputArray) = true
. Strings can be rearranged in the following way:"aa", "ab", "bb"
.
I found an exponential-time algorithm, but is there a polynomial-time algorithm? Is this problem NP-complete?
I know that a closely related problem, the Hamming Salesman Problem (HTSP), is NP-complete, and this problem is certainly reducible to HTSP, but I don't know if HTSP is reducible to this one.
No correct solution