All words contain only lowercase alphabetic characters.
这个题目应该算是leetcode上比较难的题目了。刚开始我采用了和Word Ladder相似的做法，只是用ArrayList记录了当前变换路径，在小数据的情况下可以Accept，但是大数据超时。究其原因，是由于为每个当前节点记录变换路径的时候，需要复制之前的ArrayList，这个时间开销较大。
同时，我利用了两个ArrayList，交替记录上一层和下一层的节点，如果下一层节点为空，则不存在路径，立即返回。如果下一层中出现了end，证明找到了所有的最短路径，停止搜索开始构造路径。实现代码如下：
1 public class WordLadderII {
2 private void GeneratePath(Map<String, ArrayList<String>> prevMap,
3 ArrayList<String> path, String word,
4 ArrayList<ArrayList<String>> ret) {
5 if (prevMap.get(word).size() == 0) {
6 path.add(0, word);
7 ArrayList<String> curPath =
new ArrayList<String>(path);
8 ret.add(curPath);
9 path.remove(0);
10 return;
11 }
12 13 path.add(0, word);
14 for (String pt : prevMap.get(word)) {
15 GeneratePath(prevMap, path, pt, ret);
16 }
17 path.remove(0);
18 }
19 20 public ArrayList<ArrayList<String>> findLadders(String start, String end,
21 HashSet<String> dict) {
22 ArrayList<ArrayList<String>> ret =
new ArrayList<ArrayList<String>>();
23 Map<String, ArrayList<String>> prevMap =
new HashMap<String, ArrayList<String>>();
24 dict.add(start);
25 dict.add(end);
26 for (String d : dict) {
27 prevMap.put(d,
new ArrayList<String>());
28 }
29 ArrayList<HashSet<String>> candidates =
new ArrayList<HashSet<String>>();
30 candidates.add(
new HashSet<String>());
31 candidates.add(
new HashSet<String>());
32 int current = 0;
33 int previous = 1;
34 candidates.get(current).add(start);
35 while (
true) {
36 current = current == 0 ? 1 : 0;
37 previous = previous == 0 ? 1 : 0;
38 for (String d : candidates.get(previous)) {
39 dict.remove(d);
40 }
41 candidates.get(current).clear();
42 for (String wd : candidates.get(previous)) {
43 for (
int pos = 0; pos < wd.length(); ++pos) {
44 StringBuffer word =
new StringBuffer(wd);
45 for (
int i = 'a'; i <= 'z'; ++i) {
46 if (wd.charAt(pos) == i) {
47 continue;
48 }
49 50 word.setCharAt(pos, (
char) i);
51 52 if (dict.contains(word.toString())) {
53 prevMap.get(word.toString()).add(wd);
54 candidates.get(current).add(word.toString());
55 }
56 }
57 }
58 }
59 60 if (candidates.get(current).size() == 0) {
61 return ret;
62 }
63 if (candidates.get(current).contains(end)) {
64 break;
65 }
66 }
67 68 ArrayList<String> path =
new ArrayList<String>();
69 GeneratePath(prevMap, path, end, ret);
70 71 return ret;
72 }
73 }