LeetCode_127_Word Ladder (Java)

127. Word Ladder

Hard

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.

Example 1:

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

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 valid transformation sequence.

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

문제 풀이

Wordlist에 있는 문자들로 탐색을 이어나가야하는데 하나씩 문자가 다른 것들을 찾는 bfs를 생각했다.

코드

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int cnt = 1;

        if(!wordList.contains(endWord)) return 0;

        Map<String, Integer> visited = new HashMap<>();

        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        visited.put(beginWord, 0);

        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0; i<size; i++){
                String curr = queue.poll();

                if(curr.equals(endWord)) return cnt;

                for(String next : wordList){
                    if(!visited.containsKey(next) && oneDifferent(curr, next)){
                        queue.offer(next);
                        visited.put(next, 0);
                    }
                }
            }
            cnt ++;
        }
        return 0;
    }

    boolean oneDifferent(String curr, String next) {
        if(curr.length() != next.length()) return false;

        int diffCnt = 0;
        for(int i=0; i<curr.length(); i++){
            if(curr.charAt(i) != next.charAt(i)) {
                diffCnt ++;
                if(diffCnt > 1) return false;
            }
        }
        return diffCnt == 1;
    }
}