LeetCode OJ - Word Ladder 2

  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<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
  9         
 10         //for BFS 
 11         LinkedList<String> queue = new LinkedList<String>();
 12         //store the words that have visited and in the dict, and its corresponding level
 13         HashMap<String,Integer> visited = new HashMap<String,Integer>();
 14         //the level information for every word
 15         LinkedList<Integer> level = new LinkedList<Integer>();
 16         //the word and its parents
 17         HashMap<String,ArrayList<String>> wP = new HashMap<String,ArrayList<String>>();
 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<par.length();i++){
 28                 
 29                 char[] words = par.toCharArray();
 30                 char o = words[i];//the original word
 31                 for(char c=‘a‘;c<=‘z‘;c++)
 32                 {
 33                     if(c!=o){
 34                         //subsitude by another char
 35                         words[i] = c;    
 36                         String changed = new String(words);
 37                         //the last-1 level . 
 38                         if(changed.equals(end))
 39                         {
 40                             visited.put(changed, le+1);// it.s very important!!!! Dont‘t forget!!
 41                             
 42                             if(wP.containsKey(end)){
 43                                 ArrayList<String> p = wP.get(end);
 44                                 p.add(par);
 45                                 wP.put(end, p);
 46                             }else{
 47                                 ArrayList<String> p = new ArrayList<String>();
 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<String> p = wP.get(changed);
 65                                 p.add(par);
 66                                 wP.put(changed, p);
 67                             }else{
 68                                 ArrayList<String> p = new ArrayList<String>();
 69                                 p.add(par);
 70                                 wP.put(changed, p);
 71                             }
 72                         }
 73                     }
 74                 }
 75                 
 76             }
 77         }
 78         ArrayList<ArrayList<String>> fl =new ArrayList<ArrayList<String>>();
 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<String,ArrayList<String>> wP, String word, ArrayList<ArrayList<String>> fl, 
 94             ArrayList<String> cur){
 95         if(wP.get(word)==null)
 96         {
 97             ArrayList<String> next = new ArrayList<String>();
 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<String> next = new ArrayList<String>();
106             next.add(word);
107             if(cur!=null && cur.size()>0)
108                 next.addAll(cur);
109             traceback(wP, p, fl, next);
110         }
111     }