Easy to figure out in java, which is used by spfa and map


  • 0
    W
    public class Solution {
    //The main idea is to convert it to graph, to get the min distance pathes from start to end.
    //each word can be change only one letter means they are connected. Use this character to construct map
    //use spfa to get min distance pathes between start and end. Use hashmap to remember the preNode of the curNode.
    public ArrayList<ArrayList<String>> findLadders(String start, String end, Set<String> dict) {
        ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
        ArrayList<String> cur = new ArrayList<String>();
        if(dict==null||dict.size()<1) return res;
        if(start==end){
            cur.add(start);
            res.add(cur);
            return res;
        }
        HashMap<String,ArrayList<String>> map = new HashMap<String, ArrayList<String>>();
        HashMap<String,ArrayList<String>> path = new HashMap<String,ArrayList<String>>();
        generateMap(map,dict,start,end);
        minDistancePath(map,path,start);
        cur.add(end);
        findMinPath(res,cur,path,start,end);
        return res;
    }
    public void generateMap(HashMap<String,ArrayList<String>> map,Set<String> dict,String start,String end){
        dict.add(start);
        dict.add(end);
        Iterator it = dict.iterator();
        while(it.hasNext()){
            String key = (String) it.next();
            connect(map,dict,key);
        }
    }
    public void connect(HashMap<String,ArrayList<String>> map,Set<String> dict,String key){
        map.put(key,new ArrayList<String>());
        char[] cs = key.toCharArray();
        for(int i=0;i<cs.length;++i){
            char c = cs[i];
            for(int j=0;j<26;++j){
                if(c==('a'+j)) continue;
                cs[i] = (char) ('a'+j);
                String temp = new String(cs);
                if(dict.contains(temp)) map.get(key).add(temp);
            }
            cs[i]=c;
        }
    }
    //use spfa to get min distance pathes
    public void minDistancePath(HashMap<String,ArrayList<String>> map,HashMap<String,ArrayList<String>> path,String start){
        Set<String> visit = new HashSet<String>();
        Queue<String> q = new LinkedList<String>();
        q.offer(start);
        visit.add(start);
        HashMap<String,Integer> dp = new HashMap<String,Integer>();
        for(String key:map.keySet()){
            path.put(key,new ArrayList<String>());
            if(key==start) dp.put(key,0);
            else dp.put(key,Integer.MAX_VALUE);
        }
        ArrayList<String> startNext = map.get(start);
        for(int i=0;i<startNext.size();++i){
            q.offer(startNext.get(i));
            dp.put(startNext.get(i),1);
            visit.add(startNext.get(i));
        }
        while(!q.isEmpty()){
            String pop = q.poll();
            visit.remove(pop);
            ArrayList<String> next = map.get(pop);
            for(int i=0;i<next.size();++i){
                if(dp.get(next.get(i))>dp.get(pop)+1){//update
                    dp.put(next.get(i),dp.get(pop)+1);
                    ArrayList<String> cur = new ArrayList<String>();
                    cur.add(pop);
                    path.put(next.get(i),cur);
                    if(!visit.contains(next.get(i))){
                        visit.add(next.get(i));
                        q.offer(next.get(i));
                    } 
                }else if(dp.get(next.get(i))==dp.get(pop)+1){//have same min distance path
                    path.get(next.get(i)).add(pop);
                }
            }
        }
    }
    public void findMinPath(ArrayList<ArrayList<String>> res,ArrayList<String> cur,HashMap<String,ArrayList<String>> path,String start,String end){
        if(end==start){
            res.add(cur);
        }else{
            ArrayList<String> pre = path.get(end);
            for(int i=0;i<pre.size();++i){
                ArrayList<String> next = new ArrayList<String>();
                next.add(pre.get(i));
                next.addAll(cur);
                findMinPath(res,next,path,start,pre.get(i));//dfs to get path
            }
        }
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.