class Solution {
  private static int answer;

    public static int solution(String begin, String target, String[] words) {
        answer = 0;

        // word 안에 target이 있는지 확인
        boolean canBeTarget = false;

        for (int i = 0; i < words.length; i++) {
            if (target.equals(words[i])) {
                canBeTarget = true;
                break;
            }
        }

        if (canBeTarget) {
            boolean[] visited = new boolean[words.length];
            findTargetFromBegin(target, words, visited, begin, 0);
        }


        return answer;
    }


    private static void findTargetFromBegin(String target, String[] words, boolean[] visited, String str, int cnt) {
        if (target.equals(str)) {
            answer = answer == 0 ? cnt : Math.min(answer, cnt);
            return;
        }

        if (answer != 0 && answer < cnt) {
            return;
        }


        for (int i = 0; i < words.length; i++) {
            String word = words[i];

            if (!canUseWord(word, str) || visited[i]) continue;

            visited[i] = true;
            findTargetFromBegin(target, words, visited, word, cnt + 1);
            visited[i] = false;
        }
    }

    private static boolean canUseWord(String word, String str) {
        int diffCnt = 0;
        for (int j = 0; j < word.length(); j++) {
            if (word.charAt(j) != str.charAt(j)) {
                diffCnt++;
            }

            if (diffCnt > 1) break;
        }

        return diffCnt <= 1;
    }
}