Another accepted Java solution (BFS)


  • 46
    public int ladderLength(String start, String end, Set<String> dict) {
      // Use queue to help BFS
      Queue<String> queue = new LinkedList<String>();
      queue.add(start);
      queue.add(null);
      
      // Mark visited word
      Set<String> visited = new HashSet<String>();
      visited.add(start);
      
      int level = 1;
      
      while (!queue.isEmpty()) {
        String str = queue.poll();
        
        if (str != null) {
          // Modify str's each character (so word distance is 1)
          for (int i = 0; i < str.length(); i++) {
            char[] chars = str.toCharArray();
            
            for (char c = 'a'; c <= 'z'; c++) {
              chars[i] = c;
              
              String word = new String(chars);
              
              // Found the end word
              if (word.equals(end)) return level + 1;
              
              // Put it to the queue
              if (dict.contains(word) && !visited.contains(word)) {
                queue.add(word);
                visited.add(word);
              }
            }
          }
        } else {
          level++;
          
          if (!queue.isEmpty()) { 
            queue.add(null);
          }
        }
      }
      
      return 0;
    }

  • 0
    O

    How to ensure the shortest path?


  • 10

    Hi Owls, when we perform the BFS, we will return as soon as we find a word in the dictionary that is 1 edit distance to the target word.

    It's like we try to find a person in a building, we scan all the rooms from level 1, level 2 till level 10, and we won't go to level 2 if we haven't searched all the rooms on level 1, so we make sure there's no such case where we have to go up to level 10 then come down to level 5 and find the person.

    Hope that makes sense.


  • 0
    O

    Nice! Thank you for explaining:)


  • 23
    O

    What is the purpose of adding and polling null in the queue?


  • 2

    To count the level !


  • 0
    H

    +1 for using null instead of 2 queues


  • 23
    P

    Adding and polling null is not necessary, if you can check the queue size in BFS. I modified the codes a bit and it works as well:

    public int ladderLength(String b, String e, Set<String> dict) {
        if(b.equals(e)) return 1;
        
        Queue<String> q = new LinkedList<String>();
        q.add(b);
        dict.remove(b);
    
        int level=2;
        
        while(!q.isEmpty()) {
            int sz = q.size();
            
            for(int i=0; i<sz; i++) {
                String tmp = q.poll();
                
                for(int j=0; j<tmp.length(); j++) {
                    char[] chars = tmp.toCharArray();
                    
                    for(char c='a'; c<='z'; c++) {
                        chars[j] = c;
                        String tmp2 = new String(chars);
                        
                        if(tmp2.equals(e)) return level;
                        
                        if(dict.remove(tmp2)) {
                            q.add(tmp2);
                        }
                    }
                }
            }
            
            level++;
        }
        
        return 0;
    }

  • 0
    V

    Hi @jeantimex. Thank you for the solution. What is the complexity of this solution?


  • 0
    C

    So, if we use dfs, we cannot guarantee the shortest path. Am I right? Thank you.


  • 1

    I think we can, but we need to make sure we dfs all the possible paths before we can say "I find the shortest path!". Normally dfs uses recursion, however, we can use iteration in bfs and guaranteed the shorted path, it's much better.


  • 1
    C

    Got it! dfs has a much worse runtime than bfs in this problem.


  • 0
    Z
    This post is deleted!

  • 0
    X

    clever null point to mark the end of a level!


  • 0
    N

    I don't think this solution is accepted even if I changed the set to List<string> I just copied/pasted the solution and changed the function parameter to accept List<string> and it didn't work.


  • 6
    F

    @jeantimex First, very thanks for your solution, it makes me easier to understand this question/solution. I found two things: 1. The line "if (word.equals(end)) return level + 1; " has a bug, need to check if word in dict also. 2. Plus the OJ give time limit exceeded error after I fix #1. Could you double check?


  • 0
    C
    This post is deleted!

  • 5
    X

    @foreveryoung2016 This solution worked perfectly 2 years ago when I first encountered this problem. However, obviously they changed the function params and added some nonsense test cases, making the solution exceed the time limit. Just check out the time when this solution was posted. This is a very old one.


  • 4

    Fails for this case.

    "hit"
    "cog"
    ["hot","dot","dog","lot","log"]

    Small change needed

    if (word.equals(end) && dict.contains(word)) return level + 1;
    

    But good solution overall :)


  • 0
    R

    @jeantimex
    if (word.equals(end)) return level + 1;

    should be inside if (dict.contains(word) && !visited.contains(word)), because word should be among the list of words in dict.

    Try this test case
    "hit"
    "cog"
    ["hot","dot","dog","lot","log"]


Log in to reply
 

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