Problem

Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the dictionary

Notice

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

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

考虑边界情况，如果dict为空，或start.equals(end)，则不满足BFS中循环的条件，在最后返回0.
如果是正常情况，start和end不等且dict包含转换需要的阶梯词组，那么转换次数加2，就是所求的转换序列长度。使用BFS，利用其按层次操作的性质，可以得到最优解。

第一层while循环：利用队列先进先出的原则，先用size = q.size()确定下一层for循环要从队列取出size个元素。这样可以保证这一层被完全遍历。当里面的三层for循环结束，即q的前size个元素全部遍历过之后，操作次数count++.
第二层for循环：对当前这一层的size个元素进行遍历。每次循环取出的元素存为新的字符串cur。
第三层for循环：遍历字符串cur的每个字符。
第四层for循环：将遍历到的cur的第i个字符换成从a到z的26个字母，存为新字符串word。然后查找dict里是否包含word：若存在，则从dict中删除此元素防止以后重复使用（无限循环），并将这个元素放入队列q，用于下一层的BFS循环。一旦找到和end相同的字符串，就返回转换序列长度 = 操作层数 + 2，即count+2。

Solution

public class Solution {
    public int ladderLength(String start, String end, Set<String> dict) {
        Queue<String> q = new LinkedList();
        q.offer(start);
        int count = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                String cur = q.poll();
                //里面的两次循环是将cur的每一位都替换成26个字母的情况，再去dict中查找
                for (int j = 0; j < cur.length(); j++) {
                    //在最内层的循环向q增加元素，并从dict里删除，体现bfs思想
                    for (char c = 'a'; c <= 'z'; c++) {
                        StringBuilder sb = new StringBuilder(cur);
                        sb.setCharAt(j, c);
                        String word = sb.toString();
                        if (end.equals(word)) return count+2;
                        else if (dict.contains(word)) {
                            dict.remove(word);
                            q.offer(word);
                        }
                    }
                }
            }
            count++;
        }
        return 0;
    }
}