Word Ladder

🔗 문제 링크

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

🔍 문제 설명

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

• Every adjacent pair of words differs by a single letter.

• Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.

• sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

⚠️ 제한사항

• 1 <= beginWord.length <= 10

• endWord.length = beginWord.length

• 1 <= wordList.length <= 5000

• wordList[i].length = beginWord.length

• beginWord, endWord, and wordList[i] consist of lowercase English letters.

• beginWord != endWord

• All the words in wordList are unique.

---

🗝 풀이 (언어 : Java)

BFS를 이용하면서 한글자씩 a~z까지 바꿔가면서 비교하는 구현 로직도 섞인 문제이다. 시작 단어를 큐에 넣어주고 단어 리스트들은 HashSet에 담아 반복문 안에서 만든 단어가 리스트에 있는 단어인지 조회할때 빠르게 할 수 있도록 한다. 만들어진 글자들은 큐에 담아서 해당 순서마다 카운트해서 sequence를 센다. 해당 단어를 찾으면 종료하고, 찾을 때까지 큐에 넣고 반복하다가 큐가 비어버리게 되면 만족하는 정답이 없는 경우이므로 0을 리턴한다.

import java.util.*;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Queue<String> queue = new LinkedList<>();
        // 리스트의 단어를 반복문에서 빠르게 조회하기 위한 hashset
        HashSet<String> set = new HashSet<>(wordList);
        int num = 1;
        // endword가 주어진 리스트에 없는 경우 종료
        if (!set.contains(endWord))
            return 0;
        // 시작 단어는 리스트에 없을 수도 있다. 아래 반복문에서 만족위해 넣음
        queue.add(beginWord);
        // bfs 수행
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                char[] arr = queue.poll().toCharArray();
                for (int j = 0; j < arr.length; j++) {
                    // 해당 위치의 한글자는 아래에서 다른 글자로 변경되므로 다시 되돌리기위해 보관
                    char original = arr[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        // 해당 위치 글자를 a~z 까지 바꿔볼 때 원래 글자와 같은 경우는 스킵
                        if (arr[j] == c)
                            continue;
                        // 글자를 변경해서 바뀐 String 생성
                        arr[j] = c;
                        String changed = String.valueOf(arr);
                        // 한글자씩 바꾸는 여러 단어들 중에 정답 있으면 종료, 아래 ++를 안하고 종료되므로 +1
                        if (endWord.equals(changed))
                            return num + 1;
                        // dict에 포함된 단어면 remove시 true, 아니면 false, 포함된 것이면 큐에 넣음
                        if (set.remove(changed))
                            queue.offer(changed);
                    }
                    arr[j] = original; // 해당 위치 글자 체크 끝났으므로 복구
                }
            }
            num++; // 큐에 한턴씩 추가될 떄마다 시퀀스는 +1
        }
        return 0; // 위에서 return 안되면 경우의 수가 없으므로 0
    }
}