Code Of The Day: stringsRearrangement

 Problem

DIFFICULTY: MEDIUM

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

  A 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).

Answer

from itertools import permutations as p

def stringsRearrangement(inputArray):

    for ia in p(inputArray):

        c = 0

        for i in range(len(ia) - 1):

            for j in range(len(ia[i])):

                if ia[i][j] != ia[i+1][j]: c += 1

            if ia[i] == ia[i+1]: c += 10

        if c == len(ia) - 1: return True

    return False