从零学算法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;
  }