My concise JAVA solution based on BFS and DFS


  • 60

    Explanation

    The basic idea is:

    1). Use BFS to find the shortest distance between start and end, tracing the distance of crossing nodes from start node to end node, and store node's next level neighbors to HashMap;

    2). Use DFS to output paths with the same distance as the shortest distance from distance HashMap: compare if the distance of the next level node equals the distance of the current node + 1.

    public List<List<String>> findLadders(String start, String end, List<String> wordList) {
       HashSet<String> dict = new HashSet<String>(wordList);
       List<List<String>> res = new ArrayList<List<String>>();         
       HashMap<String, ArrayList<String>> nodeNeighbors = new HashMap<String, ArrayList<String>>();// Neighbors for every node
       HashMap<String, Integer> distance = new HashMap<String, Integer>();// Distance of every node from the start node
       ArrayList<String> solution = new ArrayList<String>();
    
       dict.add(start);          
       bfs(start, end, dict, nodeNeighbors, distance);                 
       dfs(start, end, dict, nodeNeighbors, distance, solution, res);   
       return res;
    }
    
    // BFS: Trace every node's distance from the start node (level by level).
    private void bfs(String start, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance) {
      for (String str : dict)
          nodeNeighbors.put(str, new ArrayList<String>());
    
      Queue<String> queue = new LinkedList<String>();
      queue.offer(start);
      distance.put(start, 0);
    
      while (!queue.isEmpty()) {
          int count = queue.size();
          boolean foundEnd = false;
          for (int i = 0; i < count; i++) {
              String cur = queue.poll();
              int curDistance = distance.get(cur);                
              ArrayList<String> neighbors = getNeighbors(cur, dict);
    
              for (String neighbor : neighbors) {
                  nodeNeighbors.get(cur).add(neighbor);
                  if (!distance.containsKey(neighbor)) {// Check if visited
                      distance.put(neighbor, curDistance + 1);
                      if (end.equals(neighbor))// Found the shortest path
                          foundEnd = true;
                      else
                          queue.offer(neighbor);
                      }
                  }
              }
    
              if (foundEnd)
                  break;
          }
      }
    
    // Find all next level nodes.    
    private ArrayList<String> getNeighbors(String node, Set<String> dict) {
      ArrayList<String> res = new ArrayList<String>();
      char chs[] = node.toCharArray();
    
      for (char ch ='a'; ch <= 'z'; ch++) {
          for (int i = 0; i < chs.length; i++) {
              if (chs[i] == ch) continue;
              char old_ch = chs[i];
              chs[i] = ch;
              if (dict.contains(String.valueOf(chs))) {
                  res.add(String.valueOf(chs));
              }
              chs[i] = old_ch;
          }
    
      }
      return res;
    }
    
    // DFS: output all paths with the shortest distance.
    private void dfs(String cur, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance, ArrayList<String> solution, List<List<String>> res) {
        solution.add(cur);
        if (end.equals(cur)) {
           res.add(new ArrayList<String>(solution));
        } else {
           for (String next : nodeNeighbors.get(cur)) {            
                if (distance.get(next) == distance.get(cur) + 1) {
                     dfs(next, end, dict, nodeNeighbors, distance, solution, res);
                }
            }
        }           
       solution.remove(solution.size() - 1);
    }
    

  • 0
    N
    This post is deleted!

  • 1
    D

    I took away one for statement from your bfs method as below, test cases still pass. I don't see the point introducing that for loop as well as the boolean foundEnd. Let me know if I missed anything.

        // BFS: Trace every node's distance from the start node (level by level).
    private void bfs(String start, String end, Set<String> dict, HashMap<String, ArrayList<String>> nodeNeighbors, HashMap<String, Integer> distance) {
      for (String str : dict)
          nodeNeighbors.put(str, new ArrayList<String>());
    
      Queue<String> queue = new LinkedList<String>();
      queue.offer(start);
      distance.put(start, 0);
    
      while (!queue.isEmpty()) {
    
              String cur = queue.poll();
              int curDistance = distance.get(cur);                
              ArrayList<String> neighbors = getNeighbors(cur, dict);
    
              for (String neighbor : neighbors) {
                  nodeNeighbors.get(cur).add(neighbor);
                  if (!distance.containsKey(neighbor)) {
                      distance.put(neighbor, curDistance + 1);
                      if (!end.equals(neighbor))
                          queue.offer(neighbor);
                      
                  }
              }
    
      }
    }

  • 0
    D

    Thanks for providing this answer


  • 1
    I

    i think the loop for(count) iterates nodes on the same level. With or without should be fine. Just a way of implementing BFS.

    The foundEnd can make sure that: once we finish the level of nodes that has same shortest distance from startWord to endWord, we exit the bfs. We can remove it but the bfs would take longer. Removing it won't impact the correctness, as we are doing DFS for the second round. Even with more nodes in the distance map, we will still output the solution once we meet endWord, the beauty of DFS..

    What do you think? Would love to discuss as I think this solution is nice:)


  • 0
    R

    I tried to run the above code and found one minor bug

    you need to add below line in bfs()
    nodeNeighbors.put(start, new ArrayList<String>());

    without the above line it throws NullPointerException on below line:
    nodeNeighbors.get(cur).add(neighbor);


  • 0

    As @ranhar said, you have to add the first node into nodeNeighbors.


  • 10
    K

    first, nice code
    secondly: two points to explain the code for better understanding:

    if (distance.get(next) == distance.get(cur) + 1) {
                      dfs(next, end, dict, nodeNeighbors, distance, solution, res);
                  }
    
    1. in dfs , thereason for if (distance.get(next) == distance.get(cur) + 1) is just in case that the next node is the next level of current node, otherwise it can be one of the parent nodes of current node,or it is not the shortest node . Since in BFS, we record both the next level nodes and the parent node as neighbors of current node. use distance.get(cur)+1 we can make sure the path is the shortest one.

    2. in BFS , we can be sure that the distance of each node is the shortest one , because once we have visited a node, we update the distance , if we first met one node ,it must be the shortest distance. if we met the node again ,its distance must not be less than the distance we first met and set.

    then I made some improvements,since dfs cost a lot of time ,so we decide whether to add a node to the neighbors when we are in BFS, we can save a lot of time,the improved code is as below, most of them are same as the original code.But it cost 184MS, beat 50%,much faster.

    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
            List<List<String>> res = new ArrayList<List<String>>();
            if(dict==null)
                return res;
            Map<String,Integer> distance = new HashMap<String,Integer>();
            dict.add(end);
            distance.put(start,1);
    
            Map<String,Set<String>> neighbours =new HashMap<String,Set<String>>();
            LinkedList<String> queue= new LinkedList<String>();
    
            queue.add(start);
            boolean foundIt= false;
            //BFS
            while(!queue.isEmpty()){
                int qsize=queue.size();
                for(int i=0;i<qsize;i++){
                    String curword= queue.poll();
    
                    Set<String> curneighbours = gettheNeibours(curword, dict);
                    Iterator<String> iterator= curneighbours.iterator();
    		for (; iterator.hasNext();) {
    		    String nb = iterator.next();
                        if(curword.equals(end)){
                            foundIt=true;
                        }
    		    if (!distance.containsKey(nb)  ) { // visited
    			distance.put(nb, distance.get(curword) + 1);
    			queue.add(nb);
    		    } else {
                              if( distance.get(nb)!=distance.get(curword)+1)//if not shortest
    		          iterator.remove(); //remove since not shortest
    		    }
    
    	        }
    		neighbours.put(curword,curneighbours);
                }//end for(int i=0;i<qsize;i++){
                if(foundIt)
                    break;
            }//end while(!queue.isEmpty()){
            //DFS
            List<String> worklist= new ArrayList<String>();
            dfs(start,end,dict,neighbours,worklist,res);
            return res;
        }
    
        public void dfs(String curword,String end,Set<String> dict,Map<String,Set<String>> neighbours,List<String> worklist,List<List<String>> res){
    
            if(curword.equals(end)){
                worklist.add(curword);
                res.add(new ArrayList<>(worklist));
                worklist.remove(worklist.size()-1);
                return;
            }
            worklist.add(curword);
            if(neighbours.containsKey(curword)) {
                for (String nb : neighbours.get(curword)) {
                    dfs(nb, end, dict, neighbours, worklist, res);
                }
            }
            worklist.remove(worklist.size()-1);
        }
    
        public Set<String> gettheNeibours(String curword,Set<String> dict){
            Set<String> res=  new HashSet<String>();
    
            int len= curword.length();
            char[] chs= curword.toCharArray();
            for(int i=0;i<len;i++){
                char old = chs[i];
                for(char c='a';c<='z';c++){
                    chs[i]=c;
                    String composStr= String.valueOf(chs);
                    if(!composStr.equals(curword) && dict.contains(composStr))
                        res.add(composStr);
                }
                chs[i]= old;
            }
            return res;
        }
    

  • 1
    J

    @Cheng_Zhang said in My concise JAVA solution based on BFS and DFS:

    if (foundEnd)
    break;

    Why should we break here? Now maybe not all nodes in this level (which is 'count') have been examined, right? We only know this cur's neighbor is endWord, while maybe next 'cur' in the same level still has endWord as its neighbor so we got another path! Why should we jump out of the level here?


  • 0
    H
    This post is deleted!

  • 0

    @Jrui I have the same question of this segment code. Have you figure out the reason why it works? From my point of view, we can only break at least after checking all the nodes at current level.


  • 1

    @Jrui Oh, I see, he didn't use the correct Indented. Your logic is right, his code is right, just the indented a little misleading.


  • 0
    Y
    This post is deleted!

  • 0
    T

    @ChengZhang said in My concise JAVA solution based on BFS and DFS:

    solution.remove(solution.size() - 1);

    Can anyone explain what's the reason for the line of code in dfs shown below?
    -----solution.remove(solution.size() - 1);


  • 0
    C

    @tigermlt i think it's because if we went down the wrong path in the dfs and reached the end(depth-wise) and still haven't found endword, then that means the previous step is in the wrong direction, then we need to delete the last step and proceed with next neighbor.


  • 0
    H

    @KnightRider thank you for you the firstly point explaintion to make me better understand this code


Log in to reply
 

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