Simple JAVA Accepted solution using BFS queue


  • 0
    M
    public class Solution {
        public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
            Queue<String> queue = new LinkedList<String>();
           
            // count maintains the number of levels we moved in the graph. 
            int count = 1;
            
            // Return value
            int ret = 1; 
    
            // Queue the begin word
            queue.offer(beginWord);
            wordList.add(endWord);
            wordList.remove(beginWord);
            while(!queue.isEmpty()) {
                String top = queue.poll();
                count--;
                Set<String> neighbors = neighbors(top.toCharArray(), wordList);
                if(neighbors.contains(endWord)) {
                    return ret + 1;
                }
                for(String neighbor : neighbors) {
                    queue.offer(neighbor);
                }
                
                // Once we are done processing the neighbors in this level, we increment ret and set count to the number of neighbors in next level using queue size
    
                if(count == 0) {
                    ret++;
                    count = queue.size();
                }
            }
            return 0;
        }
        
        // Returns set of words that are present in wordList and can be 
        // formed by changing only one character in the string
        private Set<String> neighbors(char[] word, Set<String> wordList) {
            Set<String> ret = new HashSet<String>();
            for(int i = 0; i < word.length; i++) {
                char c = word[i];
                
                for(char j = 'a'; j <= 'z'; j++) {
                    word[i] = j;
                    String finalWord = String.valueOf(word);
                    if(wordList.contains(finalWord)) {
                        ret.add(finalWord);
                        wordList.remove(finalWord);
                    }
                }
                word[i] = c;
            }
            return ret;
        }
    }
    

Log in to reply
 

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