Given two words (beginWordandendWord), and a dictionary's word list, find the length of shortest transformation sequence frombeginWordtoendWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord="hit"
endWord="cog"
wordList=["hot","dot","dog","lot","log","cog"]

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.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

UPDATE (2017/1/20):
ThewordListparameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

tag: BFS

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (wordList == null || wordList.size() == 0 ) return 0;

        Set<String> dict = new HashSet<>();
        for (String word : wordList){
            dict.add(word);
        }
        if (!dict.contains(endWord)) return 0;

        Queue<String> q = new LinkedList<>();
        Set<String> seen = new HashSet<>();
        q.offer(beginWord);
        seen.add(beginWord);
        int step = 1;

        while (!q.isEmpty()){
            int size = q.size();

            for (int i = 0; i < size; i++){
                String cur = q.poll();


                for (int j = 0; j < cur.length(); j++){
                    for (char c = 'a'; c <= 'z'; c++){
                        String newCur = cur.substring(0, j) + c + cur.substring(j + 1);
                        if (newCur.equals(endWord)) return step + 1;

                        //System.out.println("new cur: " + newCur);
                        if (dict.contains(newCur) && !seen.contains(newCur)){
                            //System.out.println("adding new cur: " + newCur);
                            q.offer(newCur);
                            seen.add(newCur);
                        } 
                    }
                }
            }
            //System.out.println("q now: " + String.valueOf(q));
            step++;
        }

        return 0;
    }
}