CodeSignal [33/60] stringsRearrangement

Problem

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.

-Summary-

1. Import the permutation function from the itertools library in python. 

2. Use the permutation function to generate all possible permutations from the inputArray

3. For each possible permutation's tuple, check if each consecutive element is different by one character. 

   If not, it will return False.

   If all consecutive elements are differed by one character, return True.

4. After finish all loop, if we have not found any permutation tuple that satisfies the constraint, we return the False.

이번 문제를 풀면서 많이 헤매고 막혔었는데, Python library 중에서 itertools 의 permutation이라는 function을 알게 되면서 많이 도움이 되었던것 같다. 오늘도 새로운 function과 library를 배운다.

 

https://docs.python.org/2/library/itertools.html#itertools.permutations

9.7. itertools — Functions creating iterators for efficient looping — Python 2.7.18 documentation

모든 문제에 대한 저작권은 CodeSignal 회사에 있습니다. [Copyright © 2020 BrainFights Inc. All rights reserved]

https://codesignal.com/