All words contain only lowercase alphabetic characters.
這個(gè)題目應(yīng)該算是leetcode上比較難的題目了。剛開(kāi)始我采用了和Word Ladder相似的做法，只是用ArrayList記錄了當(dāng)前變換路徑，在小數(shù)據(jù)的情況下可以Accept，但是大數(shù)據(jù)超時(shí)。究其原因，是由于為每個(gè)當(dāng)前節(jié)點(diǎn)記錄變換路徑的時(shí)候，需要復(fù)制之前的ArrayList，這個(gè)時(shí)間開(kāi)銷較大。
其實(shí)，我們可以采用一個(gè)Map<String, HashSet<String>>結(jié)構(gòu)，記錄字典單詞的每一個(gè)前驅(qū)，這樣我們可以從end反向遍歷，構(gòu)造出轉(zhuǎn)換路徑。
同時(shí)，我利用了兩個(gè)ArrayList，交替記錄上一層和下一層的節(jié)點(diǎn)，如果下一層節(jié)點(diǎn)為空，則不存在路徑，立即返回。如果下一層中出現(xiàn)了end，證明找到了所有的最短路徑，停止搜索開(kāi)始構(gòu)造路徑。實(shí)現(xiàn)代碼如下：
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 }