22.01.18 - [PG] 단어 변환

[suhyunsim]

문제

• 단어 변환

핵심 아이디어

• DFS로 풀이
• words 길이 최대 50이라서 길이 51의 visited[] 생성
• dfs로 돌면서 방문했는지, 단어리스트와 비교하는 단어 철자 한 개만 다른지 확인
• 최대 길이 50 내에 단어 변환 가능하면 해당 카운트 리턴, 그렇지 않으면 0 리턴

어려운 점, 실수

풀이

package main.java.com.poogle.PG.Q43163;

public class Solution {
    static int answer;
    static boolean[] visited;

    public static void main(String[] args) {
        System.out.println(solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log", "cog"}));
        System.out.println(solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log"}));
    }

    public static int solution(String begin, String target, String[] words) {
        answer = 51;
        visited = new boolean[51];
        dfs(begin, target, words, 0);
        return answer == 51 ? 0 : answer;
    }

    private static void dfs(String begin, String target, String[] words, int cnt) {
        if (begin.equals(target)) {
            answer = Math.min(answer, cnt);
            return;
        }
        for (int i = 0; i < words.length; i++) {
            if (!visited[i] && check(begin, words[i])) {
                visited[i] = true;
                dfs(words[i], target, words, cnt + 1);
                visited[i] = false;
            }
        }
    }

    private static boolean check(String begin, String word) {
        int cnt = 0;
        for (int j = 0; j < begin.length(); j++) {
            if (begin.charAt(j) != word.charAt(j)) cnt++;
        }
        return cnt == 1;
    }
}