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:

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.

Analysis

见reference

Code

public class Solution {
    public int ladderLength(String start, String end, Set<String> dict) {
        if (start == null && end==null) return 0;
        if (start.length()==0 && end.length()==0) return 0;
        assert(start.length()==end.length());
        if (dict ==null || dict.size()==0) return 0;

        int ladderLen = 1;
        dict.add(end); //add end to dict, important!
        //use a queue for BFS
        Queue<String> queue = new LinkedList<String>();
        //keep a visited hashset to avoid repeatedly visit nodes
        Set<String> visited = new HashSet<String>();
        queue.add(start);
        visited.add(start);

        while(!queue.isEmpty()){
            ladderLen++;
            int qLen = queue.size();
            for (int i=0; i<qLen; i++){
                String strTemp = queue.poll();
                for (String nextWord:getNextWords(strTemp, dict)){
                    if(nextWord.equals(end)) return ladderLen;
                    if(visited.contains(nextWord)) continue;
                    queue.add(nextWord);
                    visited.add(nextWord);
                }
            }
        }

        return 0;
    }

    //返回所有和curr差一个字母，并且在dict里面的words
    //把每个字母替换为26个字母中的一个，检查是否在dict里面
    private Set<String> getNextWords(String curr, Set<String> dict) {
        Set<String> nextWords = new HashSet<String>();
        for (int i=0; i<curr.length(); i++){
            char[] chars = curr.toCharArray();
            for (char c = 'a'; c<='z'; c++){
                chars[i]=c;
                String temp = new String(chars);
                if (dict.contains(temp)) {nextWords.add(temp);}
            }
        }
        return nextWords;
    }
}

Note

  1. queue.offer(): Inserts the specified element into this queue if it is possible to do so immediately without violating capacity restrictions. When using a capacity-restricted queue, this method is generally preferable to add(E), which can fail to insert an element only by throwing an exception.
  2. char[] = String.toCharArray()
  3. String = new String(char[])

Reference