Word Ladder I leetcode

Given two words (beginWord and endWord), and a dictionary, 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 dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["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.

题解：

 这道题是套用BFS同时也利用BFS能寻找最短路径的特性来解决问题。

 把每个单词作为一个node进行BFS。当取得当前字符串时，对他的每一位字符进行从a~z的替换，如果在字典里面，就入队，并将下层count++，并且为了避免环路，需把在字典里检测到的单词从字典里删除。这样对于当前字符串的每一位字符安装a~z替换后，在queue中的单词就作为下一层需要遍历的单词了。

 正因为BFS能够把一层所有可能性都遍历了，所以就保证了一旦找到一个单词equals（end），那么return的路径肯定是最短的。

 reference:http://www.cnblogs.com/springfor/p/3893499.html
时间复杂度 O(string.length() * 26)

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
        if (beginWord == null || endWord == null) {
            return 0;
        }
        Queue<String> queue = new LinkedList<String>();
        queue.offer(beginWord);
        int res = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int k = 0; k < size; k++) {
                String str = queue.poll();
                for (int i = 0; i < str.length(); i++) {
                    char[] tem = str.toCharArray();
                    for (char j = 'a'; j <= 'z'; j++) {
                        tem[i] = j;
                        String cur = new String(tem);
                        if (cur.equals(endWord)) {
                            return res + 1;
                        }
                        else if (wordDict.contains(cur)) {
                            queue.offer(cur);
                            wordDict.remove(cur);
                        }
                    }
                }
            }
            res++;
        }
        return 0;
    }
    
}