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

Update 2018-9

class Solution {    public int ladderLength(String beginWord, String endWord, List
    
      wordList) {        Set
     
       dict = new HashSet<>(wordList);        if (!dict.contains(endWord)) return 0;                Set
      
        existed = new HashSet<>();        existed.add(beginWord);        int count = 1;                while (!existed.contains(endWord)) { //当existed集合里包含了endWord，跳出while循环并返回步数count            Set
       
         wanted = new HashSet<>();            for (String s: existed) {                for (int i = 0; i < s.length(); i++) {                    for (char ch = 'a'; ch <= 'z'; ch++) {                        StringBuilder sb = new StringBuilder(s);                        sb.setCharAt(i, ch);                        String str = sb.toString(); //找到了下一个词str                        if (dict.contains(str)) {   //如果下一个词在dict里，从dict放入wanted                            wanted.add(str);                            dict.remove(str);                        }                    }                }            }            //此时existed中所有词都找到了下一个词的集合，存在wanted中                        //如果wanted为空，则existed中的所有词都不存在下一个变化，return 0            if (wanted.size() == 0) return 0;                        //否则交换existed和wanted，步数count+1，继续查找下一步变化            count++;            existed = wanted;        }                return count;    }}