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 is O(N 26 L)

Code：

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        if (wordList == null) {
            return 0;
        }
        if (beginWord.equals(endWord)) {
            return 1;
        }
        int len = 1;
        HashSet<String> set = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        wordList.add(beginWord);
        wordList.add(endWord);
        queue.add(beginWord);
        set.add(beginWord);
        while (!queue.isEmpty()) {
            len++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.remove();
                for (String newWord : changeChar(word, wordList)) {
                    if (set.contains(newWord)) {
                        continue;
                    }
                    if (newWord.equals(endWord)) {
                        return len;
                    }
                    set.add(newWord);
                    queue.add(newWord);
                }
            }
        }
        return 0;
    }
     private ArrayList<String> changeChar(String word, Set<String> wordList) {
        ArrayList<String> result = new ArrayList<String>();
        for (int i = 0; i < word.length(); i++) {
            for (char c = 'a'; c <= 'z'; c++) {
                String replaced = replace(i, c, word);
                if (wordList.contains(replaced)) {
                    result.add(replaced);
                }
            }
        }
        return result;
    }

    private String replace(int i, char c, String word) {
        char[] chars = word.toCharArray();
        chars[i] = c;
        return new String(chars);
    }
}

Another one:

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        if (wordList == null) {
            return 0;
        }
        if (beginWord.equals(endWord)) {
            return 1;
        }
        int res = 1;
        Queue<String> queue = new LinkedList<>();
        HashSet<String> set = new HashSet<>();
        wordList.add(beginWord);
        wordList.add(endWord);
        queue.add(beginWord);
        set.add(beginWord);
        while (!queue.isEmpty()) {
            int size = queue.size();
            res++;
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                for (int j = 0; j < beginWord.length(); j++) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        char[] chars = cur.toCharArray();
                        chars[j] = c;
                        String next = new String(chars);
                        if (!wordList.contains(next)) {
                            continue;
                        }
                        if (set.contains(next)) {
                            continue;
                        }
                        if (next.equals(endWord)) {
                            return res;
                        }
                        queue.add(next);
                        set.add(next);
                    }
                }
            }
        }
        return 0;
    }
}