Code Fights - stringsRearrangement

README.md

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 be
  stringsRearrangement(inputArray) = false;

  All rearrangements don't satisfy the description condition.

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

  Strings can be rearranged in the following way: "aa", "ab", "bb".

Input/Output

• [time limit] 4000ms (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

strings_rearrangement.py

import itertools


def strings_rearrangement(input_array: list):
    for perm in itertools.permutations(input_array):
        if _consecutive_strings_differ_by_one_character(perm):
            return True
    return False


def _consecutive_strings_differ_by_one_character(input_array: list):
    iter_input_array = input_array[:-1]
    for i, current_str in enumerate(iter_input_array):
        next_str = input_array[i + 1]
        if not _differ_by_one_char(current_str, next_str):
            return False
    return True


def _differ_by_one_char(str1: str, str2: str):
    result = False
    for char1, char2 in zip(str1, str2):
        if char1 != char2:
            if result:
                return False
            else:
                result = True
    return result

test_strings_rearrangement.py

import unittest
from strings_rearrangement import strings_rearrangement


class TestStringsRearrangement(unittest.TestCase):
    def test_1(self):
        input_array = ["aba", "bbb", "bab"]
        result = strings_rearrangement(input_array)
        self.assertFalse(result)

    def test_2(self):
        input_array = ["ab", "bb", "aa"]
        result = strings_rearrangement(input_array)
        self.assertTrue(result)

    def test_3(self):
        input_array = ["q", "q"]
        result = strings_rearrangement(input_array)
        self.assertFalse(result)

    def test_4(self):
        input_array = ["zzzzab", "zzzzbb", "zzzzaa"]
        result = strings_rearrangement(input_array)
        self.assertTrue(result)

    def test_5(self):
        input_array = ["ab", "ad", "ef", "eg"]
        result = strings_rearrangement(input_array)
        self.assertFalse(result)

    def test_6(self):
        input_array = ["abc", "bef", "bcc", "bec", "bbc", "bdc"]
        result = strings_rearrangement(input_array)
        self.assertTrue(result)

    def test_7(self):
        input_array = ["abc", "abx", "axx", "abc"]
        result = strings_rearrangement(input_array)
        self.assertFalse(result)

    def test_8(self):
        input_array = ["abc", "abx", "axx", "abx", "abc"]
        result = strings_rearrangement(input_array)
        self.assertTrue(result)

    def test_9(self):
        input_array = ["f", "g", "a", "h"]
        result = strings_rearrangement(input_array)
        self.assertTrue(result)


if __name__ == '__main__':
    unittest.main()