leetcode word-ladder 2

题目描述

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

Only one letter can be changed at a time
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.

提示超时，求大神看一下是复杂度的问题还是循环问题

import java.util.*;
class Solution {
    public ArrayList<ArrayList<String>> findLadders(String start, String end, HashSet<String> dict) {
        if(start==null||end==null)
            return null;
        ArrayList<ArrayList<String>> res=new ArrayList<ArrayList<String>>();
        if(start==end){
            ArrayList<String> arr=new ArrayList<String>();
            arr.add(start);
            res.add(arr);
            return res;
        }
        dict.add(start);
        dict.add(end);
        HashMap<String,ArrayList<String>> rev=new HashMap<String,ArrayList<String>>();//逆向建立图
        ArrayList<String> cur=new ArrayList<String>();//当前层
        ArrayList<String> next;//下一层
        cur.add(start);
        dict.remove(start);
        while(cur.size()>0){//从start开始建立图，并逆向保存
        	next=new ArrayList<String>();
        	for(String s:cur){
        		for(int i=0;i<s.length();i++){
        			char[] ch=s.toCharArray();
        			for(char c='a';c<='z';c++){
        				if(ch[i]==c)
        					continue;
        				ch[i]=c;
        				String compare=new String(ch);
        				if(dict.contains(compare)){
                                            next.add(compare);
                                            if(!rev.containsKey(compare)){
                                                ArrayList<String> arr=new ArrayList<String>();
                                                arr.add(s);
                                                rev.put(compare,arr);
                                            }
                                            else{
                                                rev.get(compare).add(s);
                                            }
            		                }
        	                }
                        }
                }
        	for(String s:next){
        		dict.remove(s);
        	}
        	cur=next;
        }
        BFS(res,rev,end,start);
        return res;
    }
    public void BFS(ArrayList<ArrayList<String>> res,HashMap<String,ArrayList<String>> rev,String end,String start){
        Queue<Map<String, ArrayList<String>>> q= new LinkedList<Map<String,ArrayList<String>>>();//保存遍历的结点以及路径
        ArrayList<String> arr=new ArrayList<String>();
        arr.add(end);
        Map<String, ArrayList<String>> map=new HashMap<String,ArrayList<String>>();
        map.put(end,arr);
        q.add(map);
        while(!q.isEmpty()){
        	map=q.poll();
            String cur=map.entrySet().iterator().next().getKey();
            arr=map.entrySet().iterator().next().getValue();
            if(cur==start){
                res.add(arr);
            }
            else{
            	if(rev.containsKey(cur))
		            for(String s:rev.get(cur)){
		                ArrayList<String> path = new ArrayList<String>();
		                path.add(s);
		                path.addAll(arr);
		                map=new HashMap<String,ArrayList<String>>();
		                map.put(s,path);
		                q.add(map);
		            }
            }
        }
    }
}