Skip to content

Instantly share code, notes, and snippets.

@tyler-austin

tyler-austin/README.md

Created June 21, 2017 18:07
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save tyler-austin/ed5b3067c79b74748bf68cac264a318d to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save tyler-austin/ed5b3067c79b74748bf68cac264a318d to your computer and use it in GitHub Desktop.
Download ZIP
Code Fights - stringsRearrangement
Raw
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

Raw
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
Raw
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()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment