127. Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time Each intermediate word must exist in the word list For example,

Given: beginWord = "hit"

endWord = "cog"

wordList = ["hot","dot","dog","lot","log"]

As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5.

Note: Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters.

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {

        wordList.add(endWord);
        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        int len = 0;

        while(!queue.isEmpty()){
            int size = queue.size();
            len++;
            for(int i=0; i< size; i++){
                String s = queue.poll();
                if(s.equals(endWord)) return len;
                for(String n : getNext(s, wordList)){
                    queue.offer(n);
                }
            }
        }

        return 0;
    }

    private Set<String> getNext(String s, Set<String> wordList){
        char[] chars = s.toCharArray();
        Set<String> res = new HashSet<String>();
        for(int i=0; i< chars.length; i++){
            char c = chars[i];
            for(char x ='a'; x <= 'z'; x++){
                if(c == x) continue;
                chars[i] = x;
                String next = new String(chars);
                if(wordList.contains(next)){
                    res.add(next);
                    wordList.remove(next);
                }
                chars[i] = c;
            }
        }
        return res;
    }
}