127. Word Ladder

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

1. Only one letter can be changed at a time
2. 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.

Solution:
Ref: http://www.programcreek.com/2012/12/leetcode-word-ladder/

This problem can be solved using BFS. 

• The first step is to create a data structure that can hold a word and the number of steps needed to get to this word from the start word. WordNode is the data structure we'd use here.
• Create a queue of WordNode objects
• Add a node for the start word with number of steps = 1
• While the queue is not empty, poll and check if the removed node is to the end word
• If yes, return the number of steps
• Otherwise, we start a BFS transformation
• BFS:
• In order to generate the transformation sequence or ladder, we know that only one character can be changed at a time
• Therefore, loop over each character of current word and attempt to replace it with each letter in [a,z]. 
• If the transformed word formed by the step above is present in the dictionary,  add a WordNode for the new word to the queue. The number of steps = number of steps for current word + 1
• Remember to reset the replaced character in current word to continue the transformation sequence with the next character in current word
• In this process, if any transformation sequence terminates in end word, we would return the length of the ladder
• If there is no such transformation sequence, we wind up and return 0 per requirements in the question

class WordNode{
    String word;
    int numSteps;
 
    public WordNode(String word, int numSteps){
        this.word = word;
        this.numSteps = numSteps;
    }
}

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        Queue<WordNode> queue = new LinkedList<WordNode>();
        queue.add(new WordNode(beginWord, 1));
        
        while (!queue.isEmpty()) {
            WordNode node = queue.poll();
            String currentWord = node.word;
            
            if (currentWord.equals(endWord)) {
                return node.numSteps;
            }
            
            char[] currentWordChars = currentWord.toCharArray();
            
            for (int i = 0; i < currentWordChars.length; i++) {
                for (char c = 'a'; c <= 'z'; c++){
                    char temp = currentWordChars[i];
                    if (currentWordChars[i] != c) {
                        currentWordChars[i] = c;
                    }
                    
                    String newWord = new String(currentWordChars);
                    if (wordDict.contains(newWord)) {
                        queue.add(new WordNode(newWord, node.numSteps + 1));
                        wordDict.remove(newWord);
                    }
                    currentWordChars[i] = temp;
                }
            }
        }
        return 0;
    }
}