焦作网站建设服务,南宁网站建设电话咨询,大数据培训,万网博通126. 单词接龙 II 需要注意的是#xff0c;由于要找最短路径#xff0c;连接 dot 与 lot 之间的边就不可以被记录下来#xff0c;同理连接 dog 与 log 之间的边也不可以被记录。这是因为经过它们的边一定不会是最短路径。因此在广度优先遍历的时候#xff0c;需要记录的图…126. 单词接龙 II 需要注意的是由于要找最短路径连接 dot 与 lot 之间的边就不可以被记录下来同理连接 dog 与 log 之间的边也不可以被记录。这是因为经过它们的边一定不会是最短路径。因此在广度优先遍历的时候需要记录的图的关系如下图所示。 在广度优先遍历的时候我们需要记录从当前的单词 currWord 只变化了一个字符以后且又在单词字典中的单词 nextWord 之间的单向关系虽然实际上无向图但是广度优先遍历是有方向的我们解决这个问题可以只看成有向图记为 from它是一个映射关系键是单词值是广度优先遍历的时候从哪些单词可以遍历到「键」所表示的单词使用哈希表来保存。 Java代码牛逼格拉斯
class Solution {public ListListString findLadders(String beginWord, String endWord, ListString wordList) {ListListString res new ArrayList();SetString dict new HashSet(wordList);if (!dict.contains(endWord)) {return res;}MapString, Integer steps new HashMap(); MapString, SetString from new HashMap(); // 无向图记录层数boolean found bfs(beginWord, endWord, dict, steps, from); // 构建无向图if (found) {DequeString path new ArrayDeque(); // 从尾往前addpath.add(endWord);dfs(from, path, beginWord, endWord, res); // 开始回溯}return res;}private void dfs(MapString, SetString from, DequeString path, String beginWord, String cur, ListListString res) {if (cur.equals(beginWord)) {res.add(new ArrayList(path));return;}for (String precursor : from.get(cur)) { // 回溯path.addFirst(precursor);dfs(from, path, beginWord, precursor, res); // from有向图path.removeFirst();}}private boolean bfs(String beginWord, String endWord, SetString dict, MapString, Integer steps, MapString, SetString from) {int wordLen beginWord.length();int step 0;steps.put(beginWord, step); boolean found false;dict.remove(beginWord);QueueString queue new LinkedList();queue.offer(beginWord); // 用于BFS层搜索while (!queue.isEmpty()) {step;int size queue.size();for (int i 0; i size; i) { // 遍历队列这一层的String currWord queue.poll();char[] charArray currWord.toCharArray();for (int j 0; j wordLen; j) { // 单词数组char origin charArray[j];for (char c a; c z; c) { // 对单词的每一个位进行更替charArray[j] c;String nextWord String.valueOf(charArray);if (steps.containsKey(nextWord) steps.get(nextWord) step) { // 归一的时候出现即dog log到cog的时候from.get(nextWord).add(currWord); // from: 广度优先遍历的时候从哪些单词可以遍历到「键」所表示的单词} // 遍历第i层的时候step i 1; if (!dict.contains(nextWord)) { // 在当前层遍历的时候已去除自身下一层入队列并去除在dict的记录continue;}// System.out.println(nextWord);dict.remove(nextWord);queue.offer(nextWord); // 进入到此处的都是下一层的下一层入队列并记录层数。当前层的已经被过滤掉了steps.put(nextWord, step); // 记录nextWord的层数from.putIfAbsent(nextWord, new HashSet()); // from是映射图from.get(nextWord).add(currWord); // currWord映射到nextWord有向图if (nextWord.equals(endWord)) { // 不能在这里进行break要继续填充endWord的setfound true;}}charArray[j] origin;}}if (found) { // 每一层结束后判断找到最短路径退出whilebreak;}}return found;}
}
