Simple Java Solution based on BFS and DFS beats 75%


  • 0
    D
    public class Solution {
        public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
            Map<String,List<String>> map=new HashMap<>();     //map   //four important ds variable: map,results,queue,ladder
            List<List<String>> results=new ArrayList<>();       //results
            Queue<String> queue=new ArrayDeque<>();         //queue
            queue.add(beginWord);
            Map<String,Integer> ladder=new HashMap<>();     //ladder
            for(String s:wordList){
                ladder.put(s,Integer.MAX_VALUE);
            }
            ladder.put(beginWord,0);
            int min=Integer.MAX_VALUE;                  //NO.5 variable min: 
            wordList.add(endWord);
            while(!queue.isEmpty()){                          //start the process of BFS: using ladder,queue to get the map.
                String word=queue.poll();
                int step=ladder.get(word)+1;
                if(step>min) break;
                for(int i=0;i<word.length();i++){
                    StringBuilder sb=new StringBuilder(word);
                    for(char ch='a';ch<='z';ch++){
                        sb.setCharAt(i,ch);
                        String newword=sb.toString();
                        if(ladder.containsKey(newword)){
                            if(step>ladder.get(newword)) continue;
                            else if(step<ladder.get(newword)){
                                queue.add(newword); ladder.put(newword,step);
                            }
                            if(map.containsKey(newword)){
                                map.get(newword).add(word);
                            }else{
                                List<String> list=new LinkedList<>(); list.add(word);
                                map.put(newword,list);
                            }
                            if(newword==endWord) min=step;
                        }
                    }
                }
            }
            List<String> result=new LinkedList<>();           //start the process of DFS/backtrack:  using map to get the results.
            backtrack(map,results,endWord,beginWord,result);
            return results;
        }
        
        private void backtrack(Map<String,List<String>> map,List<List<String>> results, String word,String start,List<String> result){
            result.add(0,word);
            if(word.equals(start)){results.add(new ArrayList<>(result));}
            if(map.get(word)!=null){
                for(String s:map.get(word)){
                    backtrack(map,results,s,start,result);
                }
            }
            result.remove(0);
        }
    }

Log in to reply
 

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