Word Ladder

https://leetcode.com/problems/word-ladder/description/

Word Ladder - LeetCode

 

시작 단어부터 끝 단어까지 한 글자씩 변경할 때 몇 회에 변경 가능한지 묻는 문제이다. 이 때 변경 가능한 문자열은 리스트로 주어진다.

 

문제를 해결하기 위해서 BFS를 사용하여 해결하였다. 최소 거리를 묻는 문제이기 때문에 가까운 거리 부터 체크하는 BFS가 적절하고, 그래프의 형태는 각 글자를 각 알파벳으로 변경했을 때 주어진 리스트에 있는지로 확인해서 순차적으로 확인할 수 있다. 이 때 방문 체크는 문자열로 해야 하기 때문에 Set을 이용해 주었다.

import java.util.*;  
  
class Solution {  
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {  
        Queue<Object[]> que = new ArrayDeque<>();  
        Set<String> isExist = new HashSet<>();  
  
        que.add(new Object[]{beginWord, 1});  
        wordList.forEach(word -> isExist.add(word));  
  
        int answer = 0;  
        while(!que.isEmpty()){  
            Object[] info = que.poll();  
            String str = (String)info[0];  
            int cnt = (int)info[1];  
  
            if(cnt > wordList.size() + 1){  
                return answer;  
            }  
  
            if(str.equals(endWord)){  
                answer = cnt;  
                break;  
            }  
  
            char[] charArr = str.toCharArray();  
            for(int i = 0; i < charArr.length; i++){  
                char save = charArr[i];  
                for(int j = 0; j < 26; j++){  
                    charArr[i] = (char)(j + 'a');  
                    String next = new String(charArr);  
                    if(isExist.contains(next) && (charArr[i] != save)){  
                        que.add(new Object[]{next, cnt + 1});  
                        isExist.remove(next);  
                    }  
                }  
                charArr[i] = save;  
            }  
        }  
  
        return answer;  
    }  
}