本文共 3089 字，大约阅读时间需要 10 分钟。
https://oj.leetcode.com/problems/word-ladder-ii/
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) fromstart to end, such that:
- Only one letter can be changed at a time
- Each intermediate word must exist in the dictionary
For example,
Given:
start =
"hit" end =
"cog" dict =
["hot","dot","dog","lot","log"] Return
[ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]
Note:
- All words have the same length.
- All words contain only lowercase alphabetic characters.
public List<List<String>> findLadders(String start, String end, Set<String> dict)
这一题，相对于Word Ladder来说做法差不多，但难度上升了非常多。Word Ladder一题只需要有一个比较正确的BFS思路就可以了。而这一题，为求全部合法路径，单纯的BFS势必除了答案要求的路径上的空间消耗，还会产生许多别的空间消耗。单纯的BFS外加路径记录必然会造成TLE或者MLE。为了优化空间，其余别的啥都来了。首先可以考虑双向BFS，自上而下从start到end形成第一幅图，层级到出现end的一层为止，在扫的过程里反向记录，也就是start <- a <- b <- end。然而反向BFS的时候，只从最底层的end对应的节点反向BFS所有的路径。当然，这种做法。。。我还没写出来代码，就讲个理论。当然，下面要给出的一个代码则是BFS构造路径，DFS反向输出路径的做法。
先给出代码，然后说明吧：
public List > findLadders(String start, String end, Set dict) { Queue node_queue = new LinkedList (); HashMap > route_map = new HashMap >(); HashSet visited = new HashSet (); //防止循环用的。 node_queue.add(start); route_map.put(start, new LinkedList ()); while(!node_queue.isEmpty() && !route_map.containsKey(end)){ int cur_size = node_queue.size(); HashSet cur_layer = new HashSet (); for(int i = 0; i < cur_size; i++){ String cur_node = node_queue.poll(); char[] str_to_ch = cur_node.toCharArray(); for(int j = 0; j < cur_node.length(); j++){ char tmp = str_to_ch[j]; for(char c = 'a'; c <= 'z'; c++){ if(tmp == c){ continue; } str_to_ch[j] = c; String candidate = new String(str_to_ch); if(dict.contains(candidate)){ if(!visited.contains(candidate)){ visited.add(candidate); cur_layer.add(candidate); List parents = new LinkedList (); parents.add(cur_node); route_map.put(candidate, parents); node_queue.add(candidate); }else{ if(cur_layer.contains(candidate)){ route_map.get(candidate).add(cur_node); } } } } str_to_ch[j] = tmp; } } } List > res = new LinkedList >(); if(route_map.containsKey(end)){ DFS(res, route_map, new LinkedList (), end, start); } return res; } public void DFS(List > res, HashMap > route_map, LinkedList cur_res, String cur_node, String start){ if(cur_node.equals(start)){ cur_res.addFirst(cur_node); res.add(cur_res); }else{ List cur_route = route_map.get(cur_node); for(String s : cur_route){ LinkedList next = new LinkedList (cur_res); next.addFirst(cur_node); DFS(res, route_map, next, s, start); } } }
就说一下BFS是怎么形成一个可以用于DFS的图。正如你看到的我定义的HashMap<String, List<String>>，名字叫route_map。这实际上，这就是当前String作为一个节点，List<String> 对应的是上一层可以连接的节点。之所以用List<String>是因为一个当前节点可能同时对应着好几个上层绩点。这样子就很明显一幅图的样子就出来了。从end你可以反向推出上一层所有的node，然后再反向推推到start即可。
另外要注意另一个变量，就是在循环里的HashSet<String> cur_layer。因为我们用visited来标记放进过queue里的节点，但事实上，如果同一层里出现过相同的节点，那么它的路径应该也需要考虑在内而不是直接跳过（虽然不再压进队列里做下一层的BFS，因为我们可以认为路径回收并被继承了就可以了。）但如果是visited出现了curlayer没出现，就表示它在上面几层出现过了，这个时候就不需要考虑了，因为它肯定就不是最短路径了。收集完路径了，最后再从end开始DFS回收所有结果就好。
嗯，大致上就是这样。囧
转载地址：http://agaxb.baihongyu.com/