share my java solution using BFS and DFS!


  • 0
    T
    public class Solution {
        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            Set<String> set1=new HashSet<>();
            Set<String> set2=new HashSet<>();
            Set<String> dict=new HashSet<>();
            dict.addAll(wordList);
            
            List<List<String>> ListArray=new ArrayList<>();
            if(!dict.contains(endWord)) return ListArray;
            
            set1.add(beginWord);
            set2.add(endWord);
            
            Map<String, Set<String>> map=new HashMap<>();
            bfs(dict,set1,set2,map,true);
            
            List<String> reg=new ArrayList<>();
            reg.add(beginWord);
            
            dfs(map,ListArray,reg,beginWord,endWord);    
            return ListArray;
            
        }
        
        
        public void dfs(Map<String,Set<String>> map,List<List<String>> ListArray,List<String> list,String start,String end){
            
            if(start.equals(end)){
                ListArray.add(new ArrayList<>(list));
            }else{
                if(!map.containsKey(start)) return;
                
                for(String ele:map.get(start)){
                    list.add(ele);
                    dfs(map,ListArray,list,ele,end);
                    list.remove(list.size()-1);
                }
            }
            
        }
        
        
        public void bfs(Set<String> dict, Set<String> set1, Set<String> set2, Map<String, Set<String>> map,boolean forward){
            //if(set1.isEmpty()) return;
            
            if(set1.size()>set2.size()){
                bfs(dict,set2,set1,map,!forward);
                return;
            }
            
            for(String ele:set1){
                dict.remove(ele);
            }
            
            Set<String> next=new HashSet<>();
            boolean connected=false;
            for(String ele:set1){
                char[] array=ele.toCharArray();
                
                for(int i=0;i<array.length;i++){
                    char a = array[i];
                    for(char c='a';c<='z';c++){
                        array[i]=c;
                        String temp=new String(array);
                        
                        if(dict.contains(temp)||set2.contains(temp)){
                            if(set2.contains(temp)){
                                connected=true;
                            }else{
                                next.add(temp);
                            }
                            
                           String key=(forward==true)?ele:temp;
                           String value=(forward==true)?temp:ele;
                        
                           if(!map.containsKey(key)){
                               map.put(key,new HashSet<String>());
                           } 
                           map.get(key).add(value);
                           next.add(temp);
                        }
                        
                    }
                    
                    array[i]=a;
                }
            }
            if(connected==true|| next.isEmpty()) return;
            else{
                bfs(dict,next,set2,map,forward);
            }
           
        }
    }
    
    

Log in to reply
 

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