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] 3 seconds (java)

• [memory limit] 1 GB

• [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).

풀이

• 문제를 이해 못하면 오래 걸림..

// 파라미터를 전역 변수로
// 메모리 낭비 막기 위함
static String [] array;
// true 횟수
static int result = 0;

boolean solution(String[] inputArray) {
    // 전역변수 선언
    array = inputArray;
    // 횟수 초기화
    result = 0;
    
    // 가변 자료구조
    LinkedList <String> list = new LinkedList<>();
    
    for (int i = 0; i < inputArray.length; i ++) {
        // 어떤 수가 먼저 구성되어 있는지 체크용 배열
        boolean [] checker = new boolean [inputArray.length];
        // 현재 인덱스는 사용
        checker[i] = true;
        // 현재 인덱스의 수 가변 자료구조에 추가
        list.add(inputArray[i]);
        // 재귀 시작
        recursion(list, checker);
        // 현재 인덱스 사용해제
        checker[i] = false;
        // 현재 인덱스의 수 가변 자료구조에서 제거
        list.pop();
    }
    
    // true 가 1 개라도 존재하면 true
    return result > 0 ? true : false;
}

void recursion (LinkedList <String> list, boolean [] checker) {
    // 가변 자료구조가 파라미터로 들어온 배열의 길이가 같을 경우 종료
    if (list.size() == array.length) {
        // 검증
        isConsecutive(list);
        // 함수 탈출
        return;
    }
    
    // solution 함수와 동일
    for (int i = 0; i < checker.length; i ++) {
        if (!checker[i]) {
            checker[i] = true;
            list.push(array[i]);
            recursion(list, checker);
            checker[i] = false;
            list.pop();
        }
    }
}

void isConsecutive (LinkedList <String> list) {
    int length = list.size();
    
    for (int i = 0; i < length - 1; i ++) {
        // 현재 문자열
        String current = list.get(i);
        // 다음 문자열
        String next = list.get(i + 1);
        
        // 배열화
        char [] c1 = current.toCharArray();
        char [] c2 = next.toCharArray();
        
        // 서로 다른 수 인 경우 카운트
        int diffCount = 0;
        
        for (int j = 0; j < c1.length; j ++) {
            if (c1[j] != c2[j]) diffCount ++;
        }
        
        // 단 하나의 문자만 달라야하므로 1 이 아닐경우 카운트 X
        if (diffCount != 1) return;
    }
    
    result++;
}