Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time

Each intermediate word must exist in the word list

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -
>
 "hot" -
>
 "dot" -
>
 "dog" -
>
 "cog",
return its length 5.

Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.

Tips:

BFS, 每次把当前字的每个字母换一次看在不在字典里，在且不是endWord就入队，然后再换。注意要先把beginWord和endWord加入wordList。

The time complexity for 1 directional BFS isO(N26L)

Code：

public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (wordList == null) return 0;
        if (beginWord.equals(endWord)) return 1;
        Queue<String> queue = new LinkedList<>();
        Set<String> dict = new HashSet<>(wordList);
        Set<String> set = new HashSet<>();
        if (!dict.contains(endWord)) return 0;
        queue.offer(beginWord);
        int res = 1;
        set.add(beginWord);
        dict.add(beginWord);
        dict.add(endWord);
        while (!queue.isEmpty()) {
            int size = queue.size(); 
            for (int s = 0; s < size; s++) {
                String prev = queue.poll();
                for (int i = 0; i < prev.length(); i++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        String curt = prev.substring(0, i) + c + prev.substring(i + 1);
                        if (curt.equals(endWord)) return res + 1;
                        if (dict.contains(curt) && !set.contains(curt)) {
                            queue.offer(curt);
                            set.add(curt);
                        }
                    }
                }
            }
            res++;
        }
        return 0;
    }
}