프로그래머스 - 단어변환 JAVA 자바

idea

1 . words에 target이 있는지 확인- 없으면 그냥 바로 0을 return하게 했다.
2 . dfs로 돌면서 확인 해주기
3 . 한글자차이인지 체크해주기 -> check => 이건그냥 단순하게 구현함

 

count=0부터 시작해서 방문하지 않았고, 한글자 차이 밖에 안나면 count를 증가시키고 또 돌아준다. target을 찾을때까지
만약 target이랑 같으면 count값이 min인지 비교해주기

• 여기는 tmi 이 문제 풀다가 순서가 같다고 했을때 Set이랑 for문이랑 속도차이가 있는지 궁금해서 테스트를 해봤는데

배열을 set으로 바꾸는데 걸리는 시간때문에 그런지 for문이 더 빨랐음(테스트케이스 5개에 0.2초정도)

역시 당연한건가..

그냥 궁금해서 해봄

• 참고로 Array to Set은 Set set = new HashSet<>(Arrays.asList(words)); 사용함

class Solution {
    boolean [] visited;
    int answer;
    public int solution(String begin, String target, String[] words) {
        answer = 51;
        boolean flag = false;
        visited= new boolean[words.length];
        //words에 target이 있는지 확인 - set으로도 해보기
        for(int i=0;i<words.length;i++){
            if(words[i].equals(target))
                flag=true;
        }
        if(!flag)
            return 0;
        else{
           dfs(begin, target,0,words);
        }
        return answer;
    }
    public void dfs(String current, String target, int count, String[] words){
        if(current.equals(target)){
            answer= (answer>count)? count : answer;
            return;
        }
        for(int i=0;i<words.length;i++){
            if(!visited[i]&&check(words[i],current)){
                visited[i]=true;
                dfs(words[i],target,count+1,words);
                visited[i]=false;
            }
        }
    }
    public boolean check(String str, String compare){
        int count=0;
        boolean result=false;
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)!=compare.charAt(i))
                count++;
        }
        if(count==1)
            result= true;
        else
           result= false;
        return result;
    }
}