题目:
给定两个单词(beginWord 和 endWord)和一个字典 wordList,找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则:
每次转换只能改变一个字母。
转换过程中的中间单词必须是字典中的单词。
说明:
如果不存在这样的转换序列,返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 beginWord 和 endWord 是非空的,且二者不相同。
示例 1:
输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出:
[
[“hit”,“hot”,“dot”,“dog”,“cog”],
[“hit”,“hot”,“lot”,“log”,“cog”]
]
示例 2:
输入:
beginWord = “hit”
endWord = “cog”
wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
输出: []
解释: endWord “cog” 不在字典中,所以不存在符合要求的转换序列
此题考点为宽度搜索+深度搜索+常数项优化
//给定两个单词beginWord和endWord,还有一本词典是list类型。 //找到所有从beginWord变到endWord的最短转换路径 private static ArrayList<String> getNext(String word,Set<String>dict) { ArrayList<String> reS = new ArrayList<String>();//存储word的邻居 char[] chs = word.toCharArray(); //对word上每个字符从a-z都换一遍产生只有一个字符与word不一样的新单词 for(char cur = 'a';cur<='z';cur++) { for(int i = 0;i<chs.length;i++) { if(chs[i]!=cur) { char temp = chs[i]; chs[i] = cur; //在给定的字典里查有无该新单词,如有则证明该单词为word的邻居,将其加入res表 if(dict.contains(String.valueOf(chs))) reS.add(String.valueOf(chs)); chs[i] = temp; } } } return reS; } public static HashMap<String, ArrayList<String>> getNextss(List<String> words) { Set<String> dict = new HashSet<>(words);//将words的内容都放入set容器中 HashMap<String, ArrayList<String>> nexts = new HashMap<>(); //对每一个单词都在哈希表中建立对应的邻居表映射 for(int i = 0;i<words.size();i++) { nexts.put(words.get(i), new ArrayList<>()); } //对每一个单词求其邻居表,并放入哈希表中 for(int i = 0;i<words.size();i++) { nexts.put(words.get(i), getNext(words.get(i), dict)); } //返回邻居总表 return nexts; } //获取距离表,存放每个单词离begin的距离 public static HashMap<String, Integer> getDistance(String begin,HashMap<String, ArrayList<String>> nexts) { HashMap<String, Integer> distances = new HashMap<>(); distances.put(begin, 0); Queue<String>queue = new LinkedList<String>(); queue.add(begin); HashSet<String> set = new HashSet<String>();//用来判断该单词是否已访问过。 set.add(begin); //宽度优先搜索 while(!queue.isEmpty()) { String cur = queue.poll(); for(String str:nexts.get(cur)) { if(!set.contains(str)) { distances.put(str,distances.get(cur)+1); queue.add(str); set.add(str); } } } return distances; } private static void getShortestPaths(String cur,String end,HashMap<String, ArrayList<String>> nexts, HashMap<String, Integer> distances,LinkedList<String> solution, List<List<String>>res) { solution.add(cur); if(end.equals(cur)) res.add(new LinkedList<String>(solution)); else { for(String next:nexts.get(cur)) { if(distances.get(next)==distances.get(cur)+1) getShortestPaths(next, end, nexts, distances, solution, res); } } solution.pollLast(); } public static List<List<String>> findLadders(String beginWord,String endWord,List<String> wordList) { wordList.add(beginWord); HashMap<String, ArrayList<String>> nexts = getNextss(wordList); HashMap<String, Integer> distances = getDistance(beginWord, nexts); LinkedList<String> pathList = new LinkedList<String>(); List<List<String>> res = new ArrayList<List<String>>(); getShortestPaths(beginWord, endWord, nexts, distances, pathList, res); return res; }