单词接龙

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：

序列中第一个单词是 beginWord 。
序列中最后一个单词是 endWord 。
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典 wordList 中的单词。
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。

示例1:

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例2:

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

思路：

利用广度优先搜索，这样肯定是最快的，单词的集合构成了一个无向图。我们用队列进行BFS的扩散，每次得到的队列当前大小是BFS中一层的节点数目，我们在当前层进行BFS搜索时，也会把新的节点添加到队列中，但是因为我们是每次确定了当前层的大小的，所以我们不会把不同层之间的节点混淆。同时，访问过的节点我们需要标记出来。还有一个优化的点是，我们在图中进行BFS搜索下一层的节点的时候，不去遍历集合，而是通过修改当前单词本身然后利用哈希表查找新单词是否存在，这样可以在找邻居的时候降低时间复杂度。

代码：

public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList){
        //首先将wordList保存在hashset中便于判断一个字符串是否存在
        HashSet<String> wordSet=new HashSet<>(wordList);
        //特殊情况判断
        if(wordSet.size()==0||!wordSet.contains(endWord)){
            return 0;
        }
        //初始化
        int len=beginWord.length();
        wordSet.remove(beginWord);
        //用一个队列来进行BFS，用一个set来记录已经遍历过的节点
        Queue<String> queue=new LinkedList<>();
        queue.offer(beginWord);
        HashSet<String> visited=new HashSet<>();
        visited.add(beginWord);
        int index=1;
        //当队列容量为0时表示已经将全部的可达节点遍历完成
        while(queue.size()!=0){
            int currentSize=queue.size();
            //这个for循环代表的是bfs中的一层,要把当前层的全部遍历完再进行下一层遍历
            for(int i=0;i<currentSize;i++){
                //将当前队列头的字符串poll，对每个字符进行变化，在wordList中寻找所有可以匹配到的字符串加入队列
                String theWord=queue.poll();
                if(changeOneLetterToEndWord(queue,theWord,visited,endWord,wordSet)){
                    return index+1;
                }
            }
            index++;
        }
        return 0;
    }
    private boolean changeOneLetterToEndWord(Queue<String> queue,String theWord,HashSet<String> visited,String endWord
    ,HashSet<String> wordSet){
        //从当前字符theWord的每一个位置开始进行修改，从a到z
        for(int i=0;i<theWord.length();i++){
            char[] wordChar =theWord.toCharArray();
            for(char letter='a';letter<='z';letter++){
                //是自己就跳过
                if(letter==theWord.charAt(i)){continue;}

                wordChar[i]=letter;
                String nextWord=String.valueOf(wordChar);
                if(nextWord.equals(endWord)){
                    return true;
                }
                if(wordSet.contains(nextWord)&&!visited.contains(nextWord)){
                    queue.offer(nextWord);
                    visited.add(nextWord);
                }
            }
        }
        return false;
    }
}