单词接龙

127. 单词接龙 - 力扣（LeetCode）

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

• 每一对相邻的单词只差一个字母。
• 对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
• sk == endWord

给你两个单词 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" 不在字典中，所以无法进行转换。

提示：

• 1 <= beginWord.length <= 10
• endWord.length == beginWord.length
• 1 <= wordList.length <= 5000
• wordList[i].length == beginWord.length
• beginWord、endWord 和 wordList[i] 由小写英文字母组成
• beginWord != endWord
• wordList 中的所有字符串 互不相同

将单词的转换路径转换成无向图

无向图求最短路，广搜最为合适，广搜只要搜到了终点，那么一定是最短的路径。

每当第一次遇到下一个节点，就将其最短路径保存到map，最终map中的结果就是起始点到所有节点的最短路径

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordSet = new HashSet<>(wordList); //转为set，提高查找速度
        if(!wordSet.contains(endWord)) return 0;
        Map<String, Integer> map = new HashMap<>(); //存放单词和其最短路径
        Deque<String> q = new LinkedList<>(); //广搜队列
        q.offer(beginWord);
        map.put(beginWord, 1);


        while(!q.isEmpty()){
            String word = q.poll();
            int path = map.get(word); //获取到达该单词的最短路径长度，广搜第一次到达的点就是最短路径
            for(int i = 0; i < word.length(); i++){//替换单词的字母
                for(char j = 'a'; j <= 'z'; j++){
                    char[] new_word = word.toCharArray();
                    new_word[i] = j;
                    String s = String.valueOf(new_word);//替换后的新单词
                    if(s.equals(endWord)){
                        return path + 1;
                    }
                    if(wordSet.contains(s) && !map.containsKey(s)){//wordList上存在该单词且map上没有该单               
                        map.put(s, path + 1);
                        q.offer(s);
                    }

                }
            }
        }
        return 0;
    }
}