从零学算法127

127.单词接龙
字典 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 中的所有字符串 互不相同

• 根据题意，能够将该题转换为无向图，求两点间其中最小路径即可，当我们从 beginWord 遍历图时，如果用 bfs 遍历，那么当第一次遇到 endWord 时，此时的路径就是最小路径。
• 那么首先我们要知道如何确定两点间能连接，即某个字符串是否能转换为某个字符串，根据题意转换规则为只有一个字符不同，所以我们双重循环，尝试改变某个 word 的每一位字符，如果改变后的结果在 wordList 中就表示为一个能够连接的点，记录到该点的路径长度并将该点加入队列
• 由于层序遍历的特性，第一次连接某个点时，此时路径就是到该点的最小路径，所以之后再遇到该点就不记录了，我们用 map 记录 beginWord 到 word 的最小路径

•   public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 将 wordlist 转为 set
        Set<String> set = new HashSet<>();
        for(String word : wordList)set.add(word);
        // set 都中没有 endWord 那没法转
        if(!set.contains(endWord))return 0;
        // 记录 beginWord 到 word 的最小路径
        Map<String,Integer> map = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        map.put(beginWord, 1);
  
        while(!queue.isEmpty()){
            String word = queue.poll();
            int path = map.get(word);
            for(int i = 0; i < word.length(); i++){
                for(int j = 0; j < 26; j++){
                    char c = (char)(j + 'a');
                    String newWord = word.substring(0,i) + c + word.substring(i+1);
                    // 如果转换到终点了就直接返回了
                    if (newWord.equals(endWord)) return path + 1;
                    // 如果能转换为某个点并且是第一次转换（此时路径最短）
                    if (set.contains(newWord) && !map.containsKey(newWord)){
                        map.put(newWord, path + 1);
                        queue.offer(newWord);
                    }
                }
            }
        }
        return 0;
    }