Simple Java BFS solution with explanation


  • 30
    G

    The first intuition for this problem is to build a graph whose nodes represent strings and edges connect strings that are only 1 character apart, and then we apply BFS from the startWord node. If we find the endWord, we return the level count of the bfs. This intuition is correct, but there are some places that we can save time.

    1. When we build adjacency list graph, we don't use two loops to check every pair of string to see if they are 1 character apart. Instead, we make changes to current string to obtain all the strings we can reach from current node, and see if it is in the wordList. Thus, there are currentString.length() * 25 case we need to check for every node. This is faster when the wordList set is large, since the check-every-pair method need wordList.size() * currentString.length() for each node. Otherwise, your may exceed the running time limit.

    2. For the strings we visited, we remove it from the wordList. This way we don't need to mark visited using another HashSet or something.

    1. Actually, we don't even need to build the adjacency list graph explicitly using a HashMap<String, ArrayList<String>>, since we keep all the nodes we can reach in the queue of each level of BFS. This can be seen as the keys of the HashMap are the strings that in the queue, and values are the strings that satisfy the 1 character apart in the wordList. Thus, we avoid the time cost of build map for those nodes we don't need to visit.

    public class Solution {

    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        wordList.add(endWord);
        Queue<String> queue = new LinkedList<String>();
        queue.add(beginWord);
        int level = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i < size; i++){
                String cur = queue.remove();
                if(cur.equals(endWord)){ return level + 1;}
                for(int j = 0; j < cur.length(); j++){
                    char[] word = cur.toCharArray();
                    for(char ch = 'a'; ch < 'z'; ch++){
                        word[j] = ch;
                        String check = new String(word);
                        if(!check.equals(cur) && wordList.contains(check)){
                            queue.add(check);
                            wordList.remove(check);
                        }
                    }
                }
            }
            level++;
        }
        return 0;
    }
    

    }


  • 0
    K

    Looks like in your code the below loop is not requierd...

    for(int i = 0; i < size; i++)

    Please correct me if i am wrong.


  • 2
    Z

    it is necessary I think, because size is a counter to count how many Strings are on the same level, so the queue just pop up the number of size strings with same number of level to return


  • 0
    G

    It's very important. It make sure the word in the same level iterate in one "while" loop.
    for(int i = 0; i < size; i++),
    if not include this statement, we need another queue to store the level for each word in queue, otherwise, we can't get the right "level".


  • 0
    G

    wordList.add(endWord);
    This is not necessary.


  • 1
    T

    1.any reason for wordList.add(endWord);?

    2.in the for-loop for the character, it should be ch<='z' rather than just <


  • 0
    T

    @ttlovek998 seems "wordList.add(endWord)" could speed up the algorithm...


  • 2
    S

    With recent update from set to list, you probably need to make a few optimizations to pass test cases. (see code line 1 - 2).

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            if (!wordList.contains(endWord)) return 0;
            HashSet<String> set = new HashSet<String>(wordList);
            Queue<String> q = new LinkedList<String>();
            int length = 0;
            set.add(endWord);
            q.add(beginWord);
            
            while (!q.isEmpty()) {
                int size = q.size();
                for (int i = 0; i < size; i++) {
                    String w = q.poll();
                    if (w.equals(endWord)) return length + 1;
                    wordMatch(w, set, q);
                }
                length++;
            }
            return 0;
        }
        
        public void wordMatch(String w, Set<String> set, Queue<String> q) {
            for (int i = 0; i < w.length(); i++) {
                char[] word = w.toCharArray();
                for (int j = 0; j < 26; j++) {
                    char c = (char) ('a' + j);
                    if (word[i] == c) continue;
                    word[i] = c;
                    String s = String.valueOf(word);
                    if (set.contains(s)) {
                        set.remove(s);
                        q.offer(s);
                    }
                }
            }
        }
    

  • 0
    N

    This is required to make sure endWord is in the list.

            if(!wordList.contains(endWord)) {
                return 0;
            }
    

  • 0
    J

    what's the complexity of this code ?


  • 0
    Z

    @kapilbari yeah you are wrong; this condition is necessary and important , without this condition, level will be wrong !


  • 0
    W

    may i ash why
    "hit"
    "cog"
    ["hot","dot","dog","lot","log"]
    result is 0, not 5?

    I think hit -> hot -> dot -> dog ->cog


  • 0
    B

    @wanghp08

    It's because:

    wordList.add(endWord);
    

    It adds the endword, I guess the author thought "endWord" is not in the given dictionary.

    By the way, this solution (changing set to list for given dictionary) gets TLE now.


Log in to reply
 

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