[LeetCode] Word Ladder II

Problem:

Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

Return

  [
    ["hit","hot","dot","dog","cog"],
    ["hit","hot","lot","log","cog"]
  ]

Note:

• All words have the same length.
• All words contain only lowercase alphabetic characters

Solution:O(n)

public class Solution {
   public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {

      if(dict.size() == 0 || start == null || end == null || start.length()!=end.length() )
         return new ArrayList<ArrayList<String>>();
      

      HashMap<String, ArrayList<ArrayList<String>>> map = new HashMap<>();
      HashMap<String,Integer> pmap = new HashMap<>(); 
      LinkedList<String> queue = new LinkedList<>();
      LinkedList<Integer> distance = new LinkedList<>();
      ArrayList<String> cur = new ArrayList<>();
      cur.add(start);
      ArrayList<ArrayList<String>> list = new ArrayList<>();
      list.add(cur);
      map.put(start,list);
      queue.add(start);
      dict.add(end);
      distance.add(1);
         
      while(!queue.isEmpty()){
         String curword = queue.pop();
  int curdisct = distance.pop();
  pmap.put(curword, curdisct);
             
  if(curword.equals(end)){
     int size = curdisct;
     ArrayList<ArrayList<String>> clist = map.get(curword);
     for(int i= clist.size()-1; i>=0;i--){
        if(clist.get(i).size()!= size){
           clist.remove(i);
        }
     }
     return clist;
  }
             
  for(int i=0; i< curword.length();i++){
     char[] sets = curword.toCharArray();
     for(char c='a'; c<='z';c++ ){
        sets[i] = c;
        String newword = new String(sets);
        if(newword.equals(curword)){
           continue;
        }
        if(dict.contains(newword)){
           dict.remove(newword);
           queue.add(newword);
           distance.add(curdisct+1);
                  pmap.put(newword, curdisct+1);
                  ArrayList<ArrayList<String>> nlist = new ArrayList<>();
                  map.put(newword,nlist);
           ArrayList<ArrayList<String>> plist = map.get(curword);
           for(ArrayList<String> slist:plist){
              ArrayList<String> ns = new ArrayList<String>(slist);

              ns.add(newword);
              nlist.add(ns);
                  }
        }else if( map.get(newword)!=null){
           if(pmap.get(newword) != (pmap.get(curword)+1)){
              continue;
           }
           ArrayList<ArrayList<String>> nlist = map.get(newword);
           ArrayList<ArrayList<String>> plist = map.get(curword);
                  for(ArrayList<String> slist:plist){
                  ArrayList<String> ns = new ArrayList<String>(slist);
                     ns.add(newword);
              nlist.add(ns);
           }
        }
     }
         }
      }
      return new ArrayList<ArrayList<String>>();

   }
}