Word Ladder

• https://leetcode.com/problems/word-ladder/

Problem Description

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.

Note: Start word and end word are in the given word list.

public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
    Map<String, Integer> distance = new HashMap();
    Queue<String> queue = new LinkedList();

    queue.offer(beginWord);
    distance.put(beginWord, 0);
    wordList.remove(beginWord);

    while (!queue.isEmpty()) {
        String word = queue.poll();
        if (word.equals(endWord))
            break;

        for (int i = 0; i < word.length(); i++) {
            char[] charArray = word.toCharArray();

            for (char k = 'a'; k <= 'z'; k++) {
                charArray[i] = k;
                String newWord = String.valueOf(charArray);

                if (wordList.contains(newWord)) {
                    int length = distance.get(word);
                    distance.put(newWord, length + 1);
                    queue.offer(newWord);
                    wordList.remove(newWord);
                }
            }
        }
    }

    if (distance.containsKey(endWord)) {
        return distance.get(endWord) + 1;
    } else {
        return 0;
    }        
}