关于leetcode:leetcode-126-Word-Ladder-II-单词接龙-II困难

标签: 搜寻

https://leetcode.cn/problems/word-ladder-ii

按字典 wordList 实现从单词 beginWord 到单词 endWord 转化，一个示意此过程的转换序列是模式上像 beginWord -> s1 -> s2 -> … -> sk 这样的单词序列，并满足：

每对相邻的单词之间仅有单个字母不同。
转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。留神，beginWord 不用是字典 wordList 中的单词。
sk == endWord
给你两个单词 beginWord 和 endWord，以及一个字典 wordList。请你找出并返回所有从 beginWord 到 endWord 的最短转换序列，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, …, sk] 的模式返回。

示例 1：

输出：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
输入：[[“hit”,”hot”,”dot”,”dog”,”cog”],[“hit”,”hot”,”lot”,”log”,”cog”]]
解释：存在 2 种最短的转换序列：
“hit” -> “hot” -> “dot” -> “dog” -> “cog”
“hit” -> “hot” -> “lot” -> “log” -> “cog”

示例 2：

输出：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
输入：[]
解释：endWord “cog” 不在字典 wordList 中，所以不存在符合要求的转换序列。

提醒：

1 <= beginWord.length <= 5
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord

wordList 中的所有单词互不雷同

咱们能够把起始字符串、终止字符串、以及单词表里所有的字符串设想成节点。若两个字符串只有一个字符不同，那它们相连。因为题目须要输入共性次数起码的所有批改形式，因而咱们能够应用广度优先搜寻，求得起始节点到终止节点的最短距离。
一个小技巧：咱们燕不是间接从起始节点进行广度优先搜寻，直到找到终止节点为止，而是从起始节点和终止节点别离进行广度优先搜寻，每次只延展以后层节点数起码的那一端，这样咱们能够缩小搜寻的总结点数。举例来说，假如最短距离为 4，如果咱们只从一端搜寻 4 层，总遍历节点数最多是 1+2+4+8+16=31，如果咱们从两端各搜寻 2 层，总遍历节点数最多为 2 * (1+2+4)=14。
搜寻完结后，咱们还须要通过回溯法来重建所有可能的门路。

public class Solution {public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {List<List<String>> ans = new ArrayList<>();
      // 优化
      Set<String> dict = new HashSet<>(wordList);
//        for (String w : wordList) {//            dict.add(w);
//        }

      if (!dict.contains(endWord)) {return ans;}
      dict.remove(beginWord);
      dict.remove(endWord);

      Set<String> q1 = new HashSet<>();
      q1.add(beginWord);
      Set<String> q2 = new HashSet<>();
      q2.add(endWord);
      Map<String, List<String>> next = new HashMap<>();
      boolean reversed = false;
      boolean found = false;
      while (!q1.isEmpty()) {Set<String> q = new HashSet<>();
          for (String w : q1) {
              String s = w;
              for (int i = 0; i < s.length(); i++) {char[] sArr = s.toCharArray();
                  char ch = sArr[i];
                  for (int j = 0; j < 26; j++) {sArr[i] = (char) (j + 'a');
                      s = String.valueOf(sArr);
                      if (q2.contains(s)) {if (reversed) {add(next, s, w);
                          } else {add(next, w, s);
                          }
                          found = true;
                      }
                      if (dict.contains(s)) {if (reversed) {add(next, s, w);
                          } else {add(next, w, s);
                          }
                          q.add(s);
                      }
                  }
                  sArr[i] = ch;
                  s = String.valueOf(sArr);
              }
          }
          if (found) {break;}
          for (String w : q) {dict.remove(w);
          }
          if (q.size() <= q2.size()) {q1 = q;} else {
              reversed = !reversed;
              q1 = q2;
              q2 = q;
          }
      }
      if (found) {Deque<String> path = new ArrayDeque<>();
          path.add(beginWord);
          backTracking(beginWord, endWord, next, path, ans);
      }
      return ans;
  }

  void backTracking(String src, String dst, Map<String, List<String>> next, Deque<String> path, List<List<String>> ans) {if (src == dst) {ans.add(new ArrayList<>(path));
          return;
      }

      for (String s : next.get(src)) {path.addLast(s);
          backTracking(s, dst, next, path, ans);
          path.removeLast();}
  }

  private void add(Map<String, List<String>> map, String key, String value) {if (!map.containsKey(key)) {map.put(key, new ArrayList<>());
      }
      map.get(key).add(value);
  }
}

2022/6/8 这道题烧脑子呀

关于leetcode:leetcode-126-Word-Ladder-II-单词接龙-II困难

一、题目粗心

二、解题思路

三、解题办法

3.1 Java 实现

四、总结小记