leetcode-Word Ladder II
题目：
Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:
1.Only one letter can be changed at a time
2.Each intermediate word must exist in the word list
For example,
Given:
beginWord = "hit"endWord = "cog"wordList = ["hot","dot","dog","lot","log"]Return
[
["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
分析：
第一感觉是dfs + backtracking，就是先用bfs求出beginWord到endWord的最短距离，然后dfs + backtracking找到不同的路径，等于这个最短距离的留下，大于的pass，果断TLE。
简单思考了下，除了可能出现环的情况会TLE外，还可以通过剪枝的方法优化——用HashMap记录每个单词和beginWord之间的距离，当dfs遍历到某个单词已经比最短距离长的时候，就不用再遍历下去了。提交，又TLE。
仔细又一想，这种剪枝等于没剪枝，想想HashMap是怎么求出来的？是在BFS的时候层序更新的，搜索到endWord的时候就停止了。所以道理上不存在比到endWord更长的一条路。问题不是出在走了更长的路，而是因为所有的路线都是从beginWword辐射出去的，dfs搜索的话有太多的岔路。
所以一个比较自然的想法是，从endWord往回找，就可以避免许多岔路。进一步的剪枝是依据HashMap里记录的距离，规定dfs的方向只往里beginWord距离更小的方向遍历。
code:
import java.io.*;import java.util.*;public class WordLadderII { public List> findLadders(String beginWord, String endWord, Set wordDict){ List> Ladders = new ArrayList>(); //优化一：BFS时记录每个单词的前驱 HashMap> preGraph = new HashMap>(); //优化二：记录每个节点的最短距离，往回找的时候可以进一步剪枝，同时在构图的过程中也避免了环的存在 HashMap distance = new HashMap(); wordDict.add(beginWord); wordDict.add(endWord); for(String word : wordDict){ preGraph.put(word, new ArrayList()); } //build the graph, get the preGraph and distance bfs(preGraph, distance, beginWord, wordDict); //find all the shortest path //List path = new ArrayList(); dfs(Ladders, new ArrayList(), endWord, beginWord, distance, preGraph); return Ladders; } /* *寻找差异为一的单词有两种方法： *(1)将目标单词与字典里的所有单词比较，O(n*l), n是字典容量(1000+),l是单词长度； *(2)将目标的字母用'a'-'z'挨个替换，利用Set.contains()函数搜索。由于Set.contains()是O(1)的，这种方法是O(26*l) */ public List getNextWords(String words, Set wordDict){ List nextWords = new ArrayList(); for(int i = 0; i > preGraph, HashMap distance, String beginWord, Set wordDict){ LinkedList queue = new LinkedList(); queue.offer(beginWord); distance.put(beginWord, 0); while(!queue.isEmpty()){ String curr = queue.poll(); for(String next : getNextWords(curr, wordDict)){ preGraph.get(next).add(curr); if(!distance.containsKey(next)){ distance.put(next, distance.get(curr) + 1); //保证每个单词之进入队列一次 queue.offer(next); } } } } public void dfs(List> Ladders, List path, String curr, String beginWord, HashMap distance, HashMap> preGraph){ if(curr.equals(beginWord)){ path.add(curr); Collections.reverse(path); Ladders.add(path); //Collections.reverse(path) //path.remove(path.size() - 1) return; } for(String next : preGraph.get(curr)){ //剪枝，去掉非最短路的情况 if(distance.get(curr) - 1 == distance.get(next)){ path.add(curr); //如果这里直接用path而不是new ArrayList(path), 68行的代码就需要执行了 dfs(Ladders, new ArrayList(path), next, beginWord, distance, preGraph); path.remove(path.size() - 1); } } } public static void main(String[] args){ Set dict = new HashSet(); dict.add("hot"); dict.add("dot"); dict.add("dog"); dict.add("lot"); dict.add("log"); WordLadderII WL = new WordLadderII(); List> ladders = WL.findLadders("hit","cog",dict); for(List list : ladders){ System.out.println(list); } }}时间复杂度方面：
(1)bfs构图的过程中，每个点进入队列一次，时间是O(n);
(2)dfs找路线的时候最坏情况是O(n^2),平均时间复杂度是O(n).
关键字：产品经理
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！