33. stringsRearrangement

Task

Given an array of equal-length strings, you’d like to know if it’s possible to rearrange the order of the elements in such a way that each consecutive pair of strings differ by exactly one character. Return true if it’s possible, and false if not.

Note: You’re only rearranging the order of the strings, not the order of the letters within the strings!

Example

• For inputArray = [“aba”, “bbb”, “bab”], the output should be
  stringsRearrangement(inputArray) = false.

  There are 6 possible arrangements for these strings:

  [“aba”, “bbb”, “bab”] [“aba”, “bab”, “bbb”] [“bbb”, “aba”, “bab”] [“bbb”, “bab”, “aba”] [“bab”, “bbb”, “aba”] [“bab”, “aba”, “bbb”]
  None of these satisfy the condition of consecutive strings differing by 1 character, so the answer is false.

• For inputArray = [“ab”, “bb”, “aa”], the output should be
  stringsRearrangement(inputArray) = true.

  It’s possible to arrange these strings in a way that each consecutive pair of strings differ by 1 character (eg: “aa”, “ab”, “bb” or “bb”, “ab”, “aa”), so return true.

Input/Output

• [execution time limit]
  4 seconds (py3)

• [input] array.string inputArray
  AA non-empty array of strings of lowercase letters.
  Guaranteed constraints: 2 ≤ inputArray.length ≤ 10, 1 ≤ inputArray[i].length ≤ 15.

• [output] boolean
  Return true if the strings can be reordered in such a way that each neighbouring pair of strings differ by exactly one character (false otherwise).

My Solution

def stringsRearrangement(inputArray):

    def checkDiffByOneChar(w1, w2):
        count = 0
        for i, c in enumerate(w1):
            if c != w2[i]:
                count += 1
            if count > 1:
                return False
        return count == 1

    nodes = []
    for i, w1 in enumerate(inputArray):
        neighbors = []
        for j, w2 in enumerate(inputArray):
            if checkDiffByOneChar(w1, w2):
                neighbors.append(j)
        nodes.append(neighbors)
    path = []


    def walkPath(n, path):
        path.append(n)

        if len(path) == len(nodes):
            print("path walked. path = {}".format(path))
            return True

        for i in nodes[n]:
            if i not in path:
                if walkPath(i, path):
                    return True
        path.pop()
        return False

    for start in range(len(nodes)):
        if walkPath(start, path):
            return True

    return False