1+ package Algorithms .string ;
2+
3+ import java .util .ArrayList ;
4+ import java .util .HashMap ;
5+ import java .util .HashSet ;
6+ import java .util .LinkedList ;
7+ import java .util .List ;
8+ import java .util .Queue ;
9+ import java .util .Set ;
10+
11+ public class FindLadders {
12+ public static void main (String []strs ) {
13+ Set <String >dict =new HashSet <String >();
14+ dict .add ("hot" );
15+ dict .add ("dot" );
16+ dict .add ("dog" );
17+ dict .add ("lot" );
18+ dict .add ("log" );
19+ dict .add ("cog" );
20+
21+ System .out .println (findLadders ("hit" ,"cob" ,dict ));
22+ }
23+
24+ public static List <List <String >>findLadders (String start ,String end ,Set <String >dict ) {
25+ if (start ==null ||end ==null ) {
26+ return null ;
27+ }
28+
29+ Queue <String >q =new LinkedList <String >();
30+
31+ // 存储每一个单词对应的路径
32+ HashMap <String ,List <List <String >>>map =new HashMap <String ,List <List <String >>>();
33+
34+ // 标记在某一层找到解
35+ boolean find =false ;
36+
37+ // store the length of the start string.
38+ int lenStr =start .length ();
39+
40+ List <List <String >>list =new ArrayList <List <String >>();
41+
42+ // 唯一的路径
43+ List <String >path =new ArrayList <String >();
44+ path .add (start );
45+ list .add (path );
46+
47+ // 将头节点放入
48+ map .put (start ,list );
49+ q .offer (start );
50+
51+ while (!q .isEmpty ()) {
52+ int size =q .size ();
53+
54+ HashMap <String ,List <List <String >>>mapTmp =new HashMap <String ,List <List <String >>>();
55+ for (int i =0 ;i <size ;i ++) {
56+ // get the current word.
57+ String str =q .poll ();
58+ for (int j =0 ;j <lenStr ;j ++) {
59+ StringBuilder sb =new StringBuilder (str );
60+ for (char c ='a' ;c <='z' ;c ++) {
61+ sb .setCharAt (j ,c );
62+ String tmp =sb .toString ();
63+
64+ // 1. 重复的单词，不需要计算。因为之前一层出现过，再出现只会更长
65+ // 2. 必须要在字典中出现
66+ if (map .containsKey (tmp ) || (!dict .contains (tmp ) && !tmp .equals (end ))) {
67+ continue ;
68+ }
69+
70+ // 将前节点的路径提取出来
71+ List <List <String >>pre =map .get (str );
72+
73+ // 从mapTmp中取出节点，或者是新建一个节点
74+ List <List <String >>curList =mapTmp .get (tmp );
75+ if (curList ==null ) {
76+ // Create a new list and add to the end word.
77+ curList =new ArrayList <List <String >>();
78+ mapTmp .put (tmp ,curList );
79+
80+ // 将生成的单词放入队列，以便下一次继续变换
81+ // 放在这里可以避免Q重复加入
82+ q .offer (tmp );
83+ }
84+
85+ // 将PRE的path 取出，加上当前节点，并放入curList中
86+ for (List <String >pathPre :pre ) {
87+ List <String >pathNew =new ArrayList <String >(pathPre );
88+ pathNew .add (tmp );
89+ curList .add (pathNew );
90+ }
91+
92+ if (tmp .equals (end )) {
93+ find =true ;
94+ }
95+ }
96+ }
97+ }
98+
99+ if (find ) {
100+ return mapTmp .get (end );
101+ }
102+
103+ // 把当前层找到的解放在MAP中。
104+ // 使用2个map的原因是：在当前层中，我们需要把同一个单词的所有的解全部找出来.
105+ map .putAll (mapTmp );
106+ }
107+
108+ // 返回一个空的结果
109+ return new ArrayList <List <String >>();
110+ }
111+ }