个人感觉思路比较清晰的word ladder II解法 by Java， 欢迎大家来讨论其他更好方法

1. public class Solution {
   
2.     public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
   
3.     // Start typing your Java solution below
   
4.     // DO NOT write main() function
   
5.     // method would be similar, except that, we need to store the path
   
6.     // in addition, if we get the result, we didn't stop until we finish
   
7.     // all the path of the same length
   
8.     // visited map the string to the list of its ancestor
   
9.     HashMap<String, HashSet<String>> visited=new HashMap<String, HashSet<String>>();
   
10.     HashMap<String, Integer> level=new HashMap<String, Integer>();
    
11.     LinkedList<String> queue=new LinkedList<String>();
    
12.     ArrayList<ArrayList<String>> result=new ArrayList<ArrayList<String>>();
    
13.     if (start==null || end==null || start.length()!=end.length())
    
14.     {
    
15.         return result;
    
16.     }
    
17.     // we also need to store the path for the start
    
18.     HashSet<String> path=new HashSet<String>();
    
19.     // we record the minimal length we get
    
20.     int min_length=Integer.MAX_VALUE;
    
21.     visited.put(start, path);
    
22.     level.put(start, 1);
    
23.     queue.add(start);
    
24.     while(!queue.isEmpty())
    
25.     {
    
26.         String s=queue.remove();
    
27.         char[] chars=s.toCharArray();
    
28.         for (int i=0; i<s.length(); i++)
    
29.         {
    
30.             char old=chars[i];
    
31.             for (char c='a'; c<='z'; c++)
    
32.             {
    
33.                 chars[i]=c;
    
34.                 String s2=new String(chars);
    
35.                 // avoid circle
    
36.                 // check whether it is in the dictionary
    
37.                 // we only add the string which is nearer to the start
    
38.                 if (dict.contains(s2) && (!level.containsKey(s2) || (level.containsKey(s2) && level.get(s2)>level.get(s))))
    
39.                 {
    
40.                     // we update the ancestor of the string
    
41.                     if (visited.containsKey(s2))
    
42.                     {
    
43.                         visited.get(s2).add(s);
    
44.                     }
    
45.                     else
    
46.                     {
    
47.                         // we haven't seen this node before
    
48.                         // thus we add it to the queue and also its ancestor
    
49.                         path=new HashSet<String>();
    
50.                         path.add(s);
    
51.                         visited.put(s2, path);
    
52.                         level.put(s2, level.get(s)+1);
    
53.                         queue.add(s2);
    
54.                     }
    
55.                 }
    
56.                 if (s2.equals(end))
    
57.                 {
    
58.                     // we found it
    
59.                     // we will use back trace to found its path to start
    
60.                     if (level.get(s)<min_length)
    
61.                     {
    
62.                         // it is shortest path
    
63.                         ArrayList<String> entry=new ArrayList<String>();
    
64.                         entry.add(end);
    
65.                         result.addAll(back_trace(s, visited, entry));
    
66.                         min_length=level.get(s)+1;
    
67.                     }
    
68.                     else
    
69.                     {
    
70.                         // ok, all the remaining path should be longer
    
71.                         break;
    
72.                     }
    
73.                 }
    
74.             }
    
75.             chars[i]=old;
    
76.         }
    
77.     }
    
78.     return result;
    
79. }
    
80. 
    
81. private ArrayList<ArrayList<String>> back_trace(String end, HashMap<String, HashSet<String>> visited, ArrayList<String> path)
    
82. {
    
83.     ArrayList<ArrayList<String>> result=new ArrayList<ArrayList<String>>();
    
84.     ArrayList<String> entry=new ArrayList<String>(path);
    
85.     entry.add(0, end);
    
86.     if (visited.get(end).size()<1)
    
87.     {
    
88.         result.add(entry);
    
89.         return result;
    
90.     }
    
91.     for (String str: visited.get(end))
    
92.     {
    
93.         result.addAll(back_trace(str, visited, entry));
    
94.     }
    
95.     return result;
    
96. }
    
97. }

复制代码

速度还不错. 刚试了试..思路嘛..不是原创吧..以前见过

如果你 写一个 graph 的类来做这题更加清楚易懂。。。。这题考察的关键就是graph search。。

这道题有没有文字讲解版本的。。