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:

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 length5.

Note:

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

Solution:

Using BFS, start from beginWord, using a queue to store all the words (it can transform to && is in the dictionary)

1. initialization:
   1. a queue to store all the words (in the dictionary) the beginWord can transform to with the same number of steps
   2. a hashset to track if the transformed words have already appeared in the previous transformation
2. for each level of queue, update length, poll out all elements in the queue
   1. if element == endWord, return length
   2. else, do further BFS, add all the words can be transformed from this word in one step to queue.
3. Time Complexity: O(26 * word_length)

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        if(wordList == null){
            return 0;
        } 
        if(beginWord.equals(endWord)){
            return 1;
        }

        Queue<String> q = new LinkedList<String>();
        HashSet<String> hs = new HashSet<String>();
        q.offer(beginWord);
        wordList.add(beginWord);
        wordList.add(endWord);
        int level = 1;
        while(!q.isEmpty()){
            level++;
            int level_len = q.size();
            for(int i = 0; i < level_len; i++){
                for(String word: getWords(q.poll(), wordList)){
                    if(hs.contains(word)){
                        continue;
                    }
                    if(word.equals(endWord)){
                        return level;
                    }
                    hs.add(word);
                    q.offer(word);
                }
            }
        }
        return 0;
    }

    public ArrayList<String> getWords(String start, Set<String> wordList){
        ArrayList<String> List = new ArrayList<String>();
            char[] word = start.toCharArray();

            for(int i = 0; i < start.length(); i++){
                for(char j = 'a'; j <= 'z'; j++){
                    if(j == word[i]){
                        continue;
                    }else{
                        word[i] = j; 
                        String tmp = new String(word);
                        if(wordList.contains(tmp)){
                            List.add(tmp);
                        }

                    }
                    word = start.toCharArray();

                }
            }
            return List;
        }

}

Reference:

http://www.jiuzhang.com/solutions/word-ladder/

http://bangbingsyb.blogspot.com/2014/11/leetcode-word-ladder-i-ii.html