[Programmers] 단어 변환 - JAVA

📚 Problem

단어 변환

• 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 찾기
• begin과 target은 같지 않습니다

📝 Solution

Key Idea

• 단어 2개를 비교하여 1개만 차이나는지 확인하는 함수를 구현 isChangedOneAlpha
• 시작단어에서 하나씩 다 비교를하며 DFS를 하는데
  • 1번 단어 -> 2번단어 & 2번단어 -> 1번단어 와 같은 중복 계산이 되어 시간초과가 납니다
  • 그래서 visted 배열을 전역이 아닌 파라미터로 전달하여 중복검사를 제외합니다

    public int solution(String begin, String target, String[] words) {
        int answer = words.length + 1;

        for (int i = 0; i < words.length; i++) {
            boolean[] visited = new boolean[words.length];
            if(isChangedOneAlpha(begin, words[i]))
                answer = Math.min(answer, DFS(words[i], target, words, i, visited, 1));
        }

        if(answer == words.length + 1)
            return 0;

        return answer;
    }

💻 Code

Solution.java

class Solution {
    public int solution(String begin, String target, String[] words) {
        int answer = words.length + 1;

        for (int i = 0; i < words.length; i++) {
            boolean[] visited = new boolean[words.length];
            if(isChangedOneAlpha(begin, words[i]))
                answer = Math.min(answer, DFS(words[i], target, words, i, visited, 1));
        }

        if(answer == words.length + 1)
            return 0;

        return answer;
    }

    private boolean isChangedOneAlpha(String current, String next) {
        int count = 0;
        for (int i = 0; i < current.length(); i++)
            if(current.charAt(i) != next.charAt(i)){
                count++;
                if (count > 1)
                    return false;
            }
        return true;
    }

    private int DFS(String current, String target, String[] words, int index, boolean[] visited, int cnt) {
        if(current.equals(target))
            return cnt;

        if(visited[index])
            return cnt;
        
        visited[index] = true;
        
        int result = 0;
        for (int i = 0; i < words.length; i++)
            if(index != i && isChangedOneAlpha(current, words[i]) && !visited[i])
                result = DFS(words[i], target, words, i, visited, cnt + 1);
        
        return result;
    }
}

SolutionTest.java

import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

public class SolutionTest {
    Solution solution;

    @BeforeEach
    public void setSol(){
        solution = new Solution();
    }

    @Test
    public void solution_1(){
        int result = solution.solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log", "cog"});
        assertEquals(4, result);
    }

    @Test
    public void solution_2(){
        int result = solution.solution("hit", "cog", new String[]{"hot", "dot", "dog", "lot", "log"});
        assertEquals(0, result);
    }
}