我发现在leetcode上做题，当我出现TLE问题时，往往是代码有漏洞，有些条件没有考虑到，这道题又验证了我这一想法。

这道题是在上一道的基础上进一步把所有可能得转换序列给出。

同样的先是BFS，与此同时需要一个hashMap记录下每个节点，和他所有父节点的对应关系，然后通过DFS，回溯所有可能的路径。

下面是AC代码。

1 /**  2      * Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end,  3      * @param start  4      * @param end  5      * @param dict  6      * @return  7      */  8     public ArrayList
     
      
       > findLadders(String start, String end, HashSet
       
         dict) {  9          10         //for BFS  11         LinkedList
        
          queue = new LinkedList
         
          (); 12         //store the words that have visited and in the dict, and its corresponding level 13         HashMap
          
            visited = new HashMap
           
            (); 14 //the level information for every word 15 LinkedList
            
              level = new LinkedList
             
              (); 16 //the word and its parents 17 HashMap
              
               
                > wP = new HashMap
                
                 
                  >(); 18 queue.offer(start); 19 level.offer(1); 20 wP.put(queue.peek(), null);//start has no parents; 21 visited.put(start, 1); 22 while(!queue.isEmpty() && (!visited.containsKey(end) || level.peek() == visited.get(end)-1)){ 23 String par = queue.poll(); 24 int le = level.poll(); 25 26 //for every character in the word 27 for(int i=0;i
                  
                    p = wP.get(end); 44 p.add(par); 45 wP.put(end, p); 46 }else{ 47 ArrayList
                   
                     p = new ArrayList
                    
                     (); 48 p.add(par); 49 wP.put(end, p); 50 } 51 } 52 //return le+1; 53 else if((visited.get(changed)==null || visited.get(changed) == le+1) && dict.contains(changed)){ 54 //the condition is very important!!! otherwise, there will be duplicate. 55 if(!visited.containsKey(changed)) 56 { 57 queue.offer(changed); 58 level.offer(le+1); 59 } 60 visited.put(changed,le+1); 61 62 //update the word and his parents information 63 if(wP.containsKey(changed)){ 64 ArrayList
                     
                       p = wP.get(changed); 65 p.add(par); 66 wP.put(changed, p); 67 }else{ 68 ArrayList
                      
                        p = new ArrayList
                       
                        (); 69 p.add(par); 70 wP.put(changed, p); 71 } 72 } 73 } 74 } 75 76 } 77 } 78 ArrayList
                        
                         
                          > fl =new ArrayList
                          
                           
                            >(); 79 //it's very important!!! to Check whether it has such path 80 if(!wP.containsKey(end)) 81 return fl; 82 traceback(wP,end,fl, null); 83 84 return fl; 85 } 86 /** 87 * DFS ,对每个节点的父节点进行深度遍历 88 * @param wP 89 * @param word 90 * @param fl 91 * @param cur 92 */ 93 private void traceback(HashMap
                            
                             
                              > wP, String word, ArrayList
                              
                               
                                > fl, 94 ArrayList
                                
                                  cur){ 95 if(wP.get(word)==null) 96 { 97 ArrayList
                                 
                                   next = new ArrayList
                                  
                                   (); 98 next.add(word); 99 if(cur!=null && cur.size()>0)100 next.addAll(cur);101 fl.add(next);102 return;103 }104 for(String p: wP.get(word)){105 ArrayList
                                   
                                     next = new ArrayList
                                    
                                     ();106 next.add(word);107 if(cur!=null && cur.size()>0)108 next.addAll(cur);109 traceback(wP, p, fl, next);110 }111 }