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:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

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

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Solution: 每个单词为一个端点，与改变一个字母的单词相连，用BFS

检查每个单词的每个字母从a到z变换后在不在词典中，而不是把单词与词典中其他每一个单词比较，这样可以减少时间复杂度

    public int ladderLength(String start, String end, List<String> dict) {
        if(dict == null || dict.size() == 0){
            return 0;
        }
        if(start.equals(end)){
            return 1;
        }

        int length = 1;
        Set<String> dicts = new HashSet<>();
        Set<String> hashset = new HashSet<String>();
        Queue<String> queue = new LinkedList<String>();

        for (String word : dict) {
            dicts.add(word);
        }

        queue.add(start);
        hashset.add(start);
        while(!queue.isEmpty()){

            int size = queue.size();
            length++;

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

                for(String nextword : nextWord(word, dicts)){

                    if(nextword.equals(end)){
                        return length;
                    }
                    if(hashset.contains(nextword)){
                        continue;
                    }
                    queue.add(nextword);
                    hashset.add(nextword);
                }
            }
        }
        return 0;
    }
    private ArrayList<String> nextWord(String word, Set<String> dict){
        ArrayList<String> nextWord = new ArrayList<String>();
        for(int i = 0; i < word.length(); i++){
            for(char c = 'a'; c <= 'z'; c++){
                if(c == word.charAt(i)){
                    continue;
                }
                String newWord = replace(word, i, c);
                if(dict.contains(newWord)){
                    nextWord.add(newWord);
                }
            }
        }
        return nextWord;
    }

    private String replace(String word, int i, char c){
        StringBuilder sb = new StringBuilder(word);
        sb.setCharAt(i, c);
        return sb.toString();
    }