游戏开发网站建设,玉溪网站建设公司哪家好,找事做搜索网站,制作网站低价文章目录1 题目理解2 BFS3 双向BFS1 题目理解
给定两个单词#xff08;beginWord 和 endWord#xff09;和一个字典#xff0c;找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则#xff1a;
每次转换只能改变一个字母。 转换过程中的中间单词必须是…
文章目录1 题目理解2 BFS3 双向BFS1 题目理解
给定两个单词beginWord 和 endWord和一个字典找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则
每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 说明:
如果不存在这样的转换序列返回 0。 所有单词具有相同的长度。 所有单词只由小写字母组成。 字典中不存在重复的单词。 你可以假设 beginWord 和 endWord 是非空的且二者不相同。
输入两个单词beginWord,endWord一个字典 规则查找从beginWord到endWord的最短转换序列。转换中每次只能变一个字母。转换过程中的单词必须是字典中的单词。 输出最短序列长度没有就返回0。
输入: beginWord “hit”, endWord “cog”, wordList [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出: 5
解释: 一个最短转换序列是 “hit” - “hot” - “dot” - “dog” - “cog”, 返回它的长度 5。
2 BFS
解法内容来源于力扣。 要求最短序列想到要用bfs。想到bfs自然想到图。题目中的图是隐形的。我们可以抽象出图。 可以将所有单词抽象为一个节点。如果两个单词之间只有一个字母不同则这两个单词之间有条边。边是双向的。 例子中的图是这样的。我们以beginWord为起点endWord为终点找到最短路径。 在建图过程中按照普通想法我们可以枚举每一对词语看他们是否相差一个字符。但这样效率太低我们可以优化图。我们可以建一个虚拟节点。对于单词hit创建3个虚拟节点it,ht,hi*。hit与这三个节点有双向边。如果词典中有一个单词能够转为hi这种格式那必然它也与hi有条双向边。
最后注意bfs找到最短路径之后因为加入了虚拟节点所以路径长度需要除以2。
class Solution {public int ladderLength(String beginWord, String endWord, ListString wordList) {if(wordListnull || !wordList.contains(endWord)){return 0;}MapString,ListString allComboDict new HashMapString,ListString();addToDict(beginWord,allComboDict);for(String w : wordList){addToDict(w,allComboDict);}QueueString queue new LinkedListString();queue.offer(beginWord);int step 0;MapString,Boolean visited new HashMapString,Boolean();while(!queue.isEmpty()){step;int size queue.size();for(int i0;isize;i){String node queue.poll();if(node.equals(endWord)){return step/21;}for(String toNode: allComboDict.get(node)){if(!visited.containsKey(toNode)){visited.put(toNode,true);queue.offer(toNode);}}}}return 0;}private void addToDict(String word,MapString,ListString allComboDict ){char[] array word.toCharArray();ListString listOfWord allComboDict.getOrDefault(word,new ArrayListString());for(int i0;iword.length();i){char ch array[i];array[i] *;String text new String(array);ListString list allComboDict.getOrDefault(text,new ArrayListString());list.add(word);allComboDict.put(text,list);listOfWord.add(text);array[i] ch;}allComboDict.put(word,listOfWord);}
}时间复杂度:O(w∗l2)O(w*l^2)O(w∗l2)w是单词个数l是每个单词的长度。 建图过程中对于每个单词需要枚举它连接到的所有虚拟节点复杂度为O(w)每个单词的长度为l复杂度为O(wl)。 bfs过程中每个节点最多有l条边。所以最终时间复杂度O(wl*l)。
3 双向BFS
根据给定字典构造的图可能会很大。BFS的搜索空间会依赖每层的分支数量增加而指数级增加。如果同时使用两个广度优先搜索。一个从beginWord开始搜索一个从endWord开始搜索。每次从两边各扩展一层节点当发现某一时刻两边都访问过同一节点时就停止搜索。
class Solution {public int ladderLength(String beginWord, String endWord, ListString wordList) {if(wordListnull || !wordList.contains(endWord)){return 0;}MapString,ListString allComboDict new HashMapString,ListString();addToDict(beginWord,allComboDict);for(String w : wordList){addToDict(w,allComboDict);}QueueString queue new LinkedListString();queue.offer(beginWord);MapString,Integer visited new HashMapString,Integer();visited.put(beginWord,1);QueueString queueEnd new LinkedListString();queueEnd.offer(endWord);MapString,Integer visitedEnd new HashMapString,Integer();visitedEnd.put(endWord,1);while(!queue.isEmpty() !queueEnd.isEmpty()){int step visiteNode(queue,visited,visitedEnd,allComboDict);if(step0){return step;}step visiteNode(queueEnd,visitedEnd,visited,allComboDict);if(step0){return step;}}return 0;}private int visiteNode(QueueString queue, MapString,Integer visited, MapString,Integer checkMap,MapString,ListString allComboDict ){int size queue.size();for(int i0;isize;i){String node queue.poll();int step visited.get(node);if(checkMap.containsKey(node)){return (visited.get(node) checkMap.get(node))/2;}for(String toNode: allComboDict.get(node)){if(!visited.containsKey(toNode)){visited.put(toNode,step1);queue.offer(toNode);}}}return -1;}private void addToDict(String word,MapString,ListString allComboDict ){char[] array word.toCharArray();ListString listOfWord allComboDict.getOrDefault(word,new ArrayListString());for(int i0;iword.length();i){char ch array[i];array[i] *;String text new String(array);ListString list allComboDict.getOrDefault(text,new ArrayListString());list.add(word);allComboDict.put(text,list);listOfWord.add(text);array[i] ch;}allComboDict.put(word,listOfWord);}
}
