127. 单词接龙

单词接龙

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

1. 每次转换只能改变一个字母。
2. 转换过程中的中间单词必须是字典中的单词。

说明:

• 如果不存在这样的转换序列，返回 0。
• 所有单词具有相同的长度。
• 所有单词只由小写字母组成。
• 字典中不存在重复的单词。
• 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 1:

输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出: 5

解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     返回它的长度 5。

思路+代码+注释：

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        /*
        思路：创建set存储字典单词，hashMap用来记录每个符合条件的单词以及到该单词的序列数。创建队列，队列初始为起始单词。
        遍历队列单词，对单词中的每个字母使用26个字符替换，替换后的单词如果在字典中存在并且和目标单词相同那么返回替换前单词的序列数+1；
        如果替换后的单词在字典中存在并且和目标单词不同，并且该单词不在map中(避免重复计数)那么将该单词添加到map中序列书为替换前单词序列书+1
         */
                HashSet<String> set=new HashSet<>();
            for (int i = 0; i < wordList.size(); i++) {
                set.add(wordList.get(i));
            }
            HashMap<String,Integer> map=new HashMap<>();
            Queue<String> queue=new LinkedList<>();
            queue.add(beginWord);
            map.put(beginWord,1);
            while (queue.size()>0)
            {
                String word=((LinkedList<String>) queue).pop();
                for (int i = 0; i < word.length(); i++) {
                    String newWord=new String(word);
                    char[] newWords=newWord.toCharArray();
                    for (char j = 'a'; j <= 'z'; j++) {
                        newWords[i]=j;
                        String s=new String(newWords);
                        if (set.contains(s) && s.equals(endWord))
                        {
                                return map.get(word)+1;
                        }
                        if (set.contains(s) && !map.containsKey(s))
                        {
                            map.put(s,map.get(word)+1);
                            ((LinkedList<String>) queue).add(s);
                        }
                    }
                }
            }
            return 0;
    }