Clear Java BFS solution (beat 87%) with optimization explanation


  • 0

    The tricky part of this solution is in the finding neighbors during BFS.

    Originally, I loop through wordList to find words that are diff by one, but it is not scaling well to large number of wordList.

    Then come to this solution to loop through 'a' - 'z' for each char and do match against wordList.
    Cause wordList is HashSet, such a match is very fast. Now this is only scale with word's length, which is much better.

    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        wordList.remove(beginWord);
        wordList.add(endWord);
        
        Queue<String> q = new LinkedList<String>();
        q.offer(beginWord);
        int level = 0;
        
        while(!q.isEmpty()) {
            int size = q.size();
            while(size-->0) {
                String word = q.poll();
                if(word.equals(endWord))
                    return level+1;
                char[] chars = word.toCharArray();
                for(int i=0; i<word.length(); i++) {
                    for(int c=0; c<26; c++) {
                        if((char)('a'+c) != word.charAt(i)) {
                            chars[i] = (char)('a'+c);
                            String newWord = new String(chars);
                            if(wordList.contains(newWord)) {
                                wordList.remove(newWord);
                                q.offer(newWord);
                            }
                            chars[i] = word.charAt(i);
                        }
                    }
                }
            }
            level++;
        }
        
        return 0;
    }

  • 0

    I have question with this solution:You checked if the newWord is in the wordList before you add it into the queue and you use queue.poll() to get the word to compare if it equals to the endWord. What if the endWord is not in the wordList? you would never find the word from the queue which equals to the endWord, because you didn't add it into the queue.

    update: I was wrong. you did add the endWord into the queue at first.


Log in to reply
 

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