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
solution(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
solution(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).

---

배열안에 있는 문자열의 순서를 재 배열해 하나씩만 차이나게 만들 수 있다면 True, 없다면 False를 return 해준다.

---

처음 생각 :

0 - 1, 2, 3 -> 1개 바뀌는 것이 있다면 계속.
1 - 0 2 3 -> 1개 바뀌는 것이 있다면 계속
2 - 0 1 3
3 - 0 1 2

이렇게 모든 과정에서 1개 바뀌는 것이 있다면 True, 없다면 False를 return 한다.

소스 코드 :

import copy

def solution(inputArray):
    cnt = 0
    sequence = []
    
    for el in inputArray :
        tmpArr = copy.deepcopy(inputArray)
        tmpArr.remove(el)
        for el2 in tmpArr :
            cnt = 0
            
            # 원소끼리 비교
            for i in range (len(el)) :
                if el[i] == el2[i] :
                    continue
                        
                else :
                    print(el, el2, "의 비교 중")
                    print(el[i], el[i], cnt)
                    cnt += 1
                        
            if cnt == 1 :
                print(el, el2, "는 하나의 원소만 다르다.")
                
        if cnt != 1 :
            print(el, "과 하나만 차이나는 문장이 없습니다.")
            return False
    
    return True

틀린 점 :

Input:

inputArray:
["ab", 
 "ad", 
 "ef", 
 "eg"]

Output:
true

Expected Output:
false

이런 예제를 판별해내지 못한다.

+ (틀린) 생각 : 비교한 처음 원소를 제거해준다면?

XXXX 재배열의 연결고리를 없애는 꼴이 될 수 있다.
[ab, aa, bb] ->
ab aa 조건 성립 = ab 삭제 -> [aa, bb]만 남아 False (실제로는 True)

삭제하는 것이 아니라, 1-2 2-1 이렇게 반복만 삭제해주면 될 것 같은데...

-> 이것도 좋은 생각이 아니었다.

def solution(inputArray):
    
    i = 0
    cnt = 0
    duplicate = False
    break_cnt = 0
    sequence = []
    
    for el in inputArray :
        
        inputArray.remove(el)
        inputArray.insert(i, list(el))
        
    for i in range (len(inputArray)) :
        for j in range (len(inputArray)) :
            
            if i == j :
                continue
                
            if sequence :
                for el in sequence :
                    if i == el[1] and j == el[0] :
                        duplicate = True
                        sequence.remove(el)
            
            if duplicate == True :
                duplicate = False
                continue
            
            for k in range(len(inputArray[0])) :
                if inputArray[i][k] != inputArray[j][k] :
                    cnt += 1
                
                if cnt > 1 :
                    cnt = 0
                    break
                        
            if cnt == 1 :
                cnt = 0
                break_cnt += 1
                sequence.append([i, j])
                break
            
    if break_cnt == len(inputArray) :
        return True
        
    else :
        print(break_cnt, sequence)
        return False   
        

-> 다른 예제를 통과하지 못한다...

다른 책과 알고리즘을 조금 살펴봐야겠다...

---

Solution

from itertools import permutations

def diff(w1, w2):
    return sum([a[0] != a[1] for a in zip(w1, w2)]) == 1

def solution(inputArray):
    for z in permutations(inputArray):
        if sum([diff(*x) for x in zip(z, z[1:])]) == len(inputArray) - 1:
            return True
    return False

나는 사실 보고도 많이 어려워서 해석해보았다...

diff 함수 :

두 인자 (여기서는 배열이 되겠다.) 를 묶어 a를 만들고,
두 인자 값이 같지 않은 것이 하나만 있다면 True, 아니면 False를 return 한다.

즉, 'aba' 'abb' 가 있다면
(a, a) -> False(0)
(b, b) -> False(0)
(a, b) -> True(1) 가 되어

sum(1) == 1
return True 가 되는 것이다.

즉, 하나만 다른지 구별해주는 함수이다.

solution 함수 :

for z in permutations(inputArray) : 
    
"""
inputArray를 순열로 나타낸다. 
inputArray = [1, 2, 3] 이라면
[(1,2,3), (1,3,2), (2,3,1), (2,1,3), (3,2,1), (3,1,2) .......] 이 된다.
"""
    if sum([diff(*x) for x in zip(z, z[1:])]) == len(inputArray) - 1:

"""
순열 z를 또 묶는다. ( ((1,2), (2,3)), ((1,3), (3,2)), ....)
(1, 2, 3) --> ((1,2), (2,3)) 이런 식으로 묶인다.

diff에 묶인 tuple을 넣어준다. -> True or False 반환
(*x) 가 가변인자라고 알고 있는데
자동으로 x[0], x[1]이 unpacking 되어 들어간다.

이 True, False 값의 합이 len(inputArray) 값보다 1 작아야만 조건을 만족한다.
"""

예제를 이용해서 풀어보겠다.

EX ) 
inputArray = ['aa', 'ab', 'bb']

for z in permutations(inputArray) : 
# permutations(inputArray) =  [('aa', 'ab', 'bb'), ('aa', 'bb', 'ab'), ('ab', 'bb', 'aa') 등...)

# z = ('aa', 'ab', 'bb') ...

    if sum(diff(*x) for x in zip(z, z[1:])]) == len(inputArray) - 1 :
    
    # x = ('aa', 'ab'), ('ab', 'bb')
    # zip을 사용하면 해당 배열이 소진되며 바뀐다. index : (0, 1) -> (1, 2)
    
    # diff(*x) -> 'aa', 'ab' 비교 == True
    # 'ab', 'bb' 비교 == True 
    # sum([True, True]) == len(inputArray) (3) - 1 -> True
    
        return True
    

배운 점들

• python의 zip 함수,

• tuple 자료형,

• [표현식 for --- in ----] for 문,

• Asterisk (*),

• permutation 순열에 대해 배웠다.

• arr = [1,2,3,4,5]
  arr[1::4] = [2, 5]
  arr[1::2] = [2, 3]
  arr[1::6] = [2]

-> 그냥 index를 반환.?

코드를 파이썬스럽게 짠다는 것...

---

참고 :
Tuple 자료형 : https://wikidocs.net/15
Asterisk(*) : https://mingrammer.com/understanding-the-asterisk-of-python/
내장 함수 zip 사용법 : https://www.daleseo.com/python-zip/