[leetcode] 127. Word Ladder

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words such that:

• The first word in the sequence is beginWord.
• The last word in the sequence is endWord.
• Only one letter is different between each adjacent pair of words in the sequence.
• Every word in the sequence is in wordList.

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.

Example 1:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: One shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog" with 5 words.

Example 2:

Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output: 0
Explanation: The endWord "cog" is not in wordList, therefore there is no possible transformation.

Constraints:

• 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 strings in wordList are unique.

wordList 에 있는 단어사전을 가지고 beginWord 에서 endWord 로 단어를 변형시키는데 걸리는 step 의 최소한의 횟수를 구하는 문제이다.

 

이때, 한 단어에서 다른 단어로 변형 가능한 조건은 단어사전에 있는 단어와 현재의 단어가 오로지 한 단어 만 달라야 한다.

 

각 단어를 그래프의 노드로 생각해보면 각 step 별로 변형 가능한 단어들을 추적해 나가다보면 최소한의 step 을 구할 수 있음을 알 수 있다.

 

 

 

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        boolean [] visited = new boolean[wordList.size()];

        Queue<String> q = new LinkedList<>();
        q.add(beginWord);

        int count = 1;

        while (q.isEmpty() == false) {
            int size = Integer.valueOf(q.size());

            for (int i = 0; i < size; i++) {
                String word = q.poll();

                if (word.equals(endWord)) {
                    return count;
                }

                for (int j = 0; j < wordList.size(); j++) {
                    String nextWord = wordList.get(j);

                    if (visited[j] == false && isTransformable(word, nextWord)) {
                        visited[j] = true;
                        q.add(nextWord);
                    }
                }
            }

            count++;
        }

        return 0;
    }

    private boolean isTransformable(String word, String s) {
        int count = 0;

        for (int i = 0; i < word.length(); i++) {
            if (word.charAt(i) != s.charAt(i)) {
                count++;
            }
        }

        return count == 1;
    }
}