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

答案

    public boolean transformable(String word1, String word2) {
        int count = 0;
        for(int i = 0; i < word1.length(); i++) {
            if(word1.charAt(i) != word2.charAt(i)) count++;
        }
        return count == 1;
    }
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Queue<String> q = new LinkedList<>();
        Queue<Integer> stepq = new LinkedList<>();
        boolean[] visited = new boolean[wordList.size()];

        int step = 1;

        q.offer(beginWord);
        stepq.offer(step++);
        int index = wordList.indexOf(beginWord);
        if(index >= 0)
            visited[index] = true;

        while(!q.isEmpty()) {
            int q_size = q.size();
            for(int i = 0; i < q_size; i++) {
                String curr = q.poll();
                int curr_step = stepq.poll();
                if(curr.equals(endWord)) {
                    return curr_step;
                }

                // Push all words curr can transform to
                for(int j = 0; j < wordList.size(); j++) {
                    String word2 = wordList.get(j);
                    if (!visited[j] && transformable(curr, word2)) {
                        q.offer(word2);
                        stepq.offer(step);
                        visited[j] = true;
                    }
                }
            }
            step++;
        }

        return 0;
    }