My java 747 ms passing solution


  • 0
    Y

    The idea is to use bfs build the graph level by level, use Map<String,Set<String>> to store the parents of string, then use dfs to find the path.

    public class Solution {
        public List<List<String>> findLadders(String start, String end, Set<String> dict) {
            List<List<String>> res=new LinkedList<>();
              List<String> list=new LinkedList<>();
              Set<String> qu=new HashSet<>();//I use a set instead of a queue to implement the bfs.
              Map<String,Set<String>> map=new HashMap<>();// store all visited strings and their parents
              map.put(start,null);
              qu.add(start);
              boolean flag=false;// to store whether one of shortest path is found or not.
              while(!qu.isEmpty()){
                  Set<String> qu1=new HashSet<>();
                  for(String temp:qu){
                  char[] charArray=temp.toCharArray();
                  for(int i=0;i<charArray.length;i++){
                      for(char j='a';j<='z';j++){
                          if(j==temp.charAt(i)) continue;
                          charArray[i]=j;
                          String str=String.valueOf(charArray);
                          if(str.equals(end)){
                              list.add(temp);
                              flag=true;
                          }
                          else{
                              if(dict.contains(str)&&!flag){
                               //IMPORTANT: even str is visited, we need to add temp as its parents.
                                  if(qu1.contains(str)){
                                     map.get(str).add(temp);
                                  }
                                  else if(!map.containsKey(str)){
                                      qu1.add(str);
                                      Set<String> myset=new HashSet<>();
                                      myset.add(temp);
                                      map.put(str,myset);
                                  }
                              }
                          }
                      }
                      charArray[i]=temp.charAt(i);
                  }
                }
                if(flag) break;// If shortest path has been found, break.
                  qu=qu1;
              }
             // build path
              for(String s:list){
                  List<String> temp=new ArrayList<>();
                  temp.add(end);
                  findPath(s,start,temp,map,res);
              }
              return res;
        }
        public void findPath(String s,String start,List<String> list,Map<String,Set<String>> map,List<List<String>> res){
            list.add(0,s);
            if(s.equals(start)){
                res.add(new ArrayList<>(list));
            }
            else{
                for(String str:map.get(s)){
                    findPath(str,start,list,map,res);
                }
            }
            list.remove(0);
        }
    }

Log in to reply
 

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