Lint Code 120. 单词接龙

虽然知道是使用bfs求树节点之间的最短路径问题但是还是码不出来，看的答案，失败，具体思路和二叉树的层次遍历近似
  1   2 
  3 import org.junit.Test;
  4 
  5 import java.util.*;
  6 
  7 public class LadderLength {
  8     /**
  9      * @param start: a string
 10      * @param end:   a string
 11      * @param dict:  a set of string
 12      * @return: An integer
 13      * <p>
 14      * 120. 单词接龙
 15      * 给出两个单词（start和end）和一个字典，找到从start到end的最短转换序列
 16      * <p>
 17      * 比如：
 18      * <p>
 19      * 1.每次只能改变一个字母。
 20      * 2.变换过程中的中间单词必须在字典中出现。
 21      * 样例
 22      * 给出数据如下：
 23      * <p>
 24      * start = "hit"
 25      * <p>
 26      * end = "cog"
 27      * <p>
 28      * dict = ["hot","dot","dog","lot","log"]
 29      * <p>
 30      * 一个最短的变换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog"，
 31      * <p>
 32      * 返回它的长度 5
 33      * <p>
 34      * 注意事项
 35      * 如果没有转换序列则返回0。
 36      * 所有单词具有相同的长度。
 37      * 所有单词都只包含小写字母。
 38      * <p>
 39      * 求图的最短路径使用bfs
 40      */
 41     public int ladderLength(String start, String end, Set<String> dict) {
 42         // write your code here
 43         if (dict == null) {
 44             return 0;
 45         }
 46         if (start.equals(end)) {
 47             return 1;
 48         }
 49         //hashSet用于过滤已经使用的dict中的元素，防止再走一遍
 50         HashSet<String> hashSet = new HashSet<>();
 51         //queue中放每一层的节点
 52         LinkedList<String> linkedList = new LinkedList<>();
 53 
 54         hashSet.add(start);
 55         linkedList.add(start);
 56         //可能dict中没有end，但是会有end的上一步的word
 57         dict.add(end);
 58 
 59         //下面开始遍历一层中所有的next，想象成一颗二叉树的层次遍历
 60         int result = 1;
 61         while (!linkedList.isEmpty()) {
 62             //遍历的层数就是路径的长度
 63             result++;
 64             int layerSize = linkedList.size();
 65             for (int i = 0; i < layerSize; i++) {
 66                 String poll = linkedList.poll();
 67                 for (String nextWord : getNextWords(poll,dict)) {
 68                     if (hashSet.contains(nextWord)) {
 69                         continue;
 70                     }
 71                     if (nextWord.equals(end)) {
 72                         return result;
 73                     }
 74                     hashSet.add(nextWord);
 75                     linkedList.add(nextWord);
 76                 }
 77             }
 78         }
 79         return 0;
 80     }
 81 
 82     private String replace(String s, int index, char c) {
 83         char[] chars = s.toCharArray();
 84         chars[index] = c;
 85         return new String(chars);
 86     }
 87 
 88     private ArrayList<String> getNextWords(String word, Set<String> dict) {
 89         char[] chars = word.toCharArray();
 90         ArrayList<String> nextWords = new ArrayList<>();
 91         for (int j = 0; j < chars.length; j++) {
 92             for (char i = 'a'; i <= 'z'; i++) {
 93                 if (chars[j] == i) {
 94                     continue;
 95                 }
 96                 String nextString = replace(word, j, i);
 97                 if (dict.contains(nextString)) {
 98                     nextWords.add(nextString);
 99                 }
100             }
101         }
102         return nextWords;
103     }
104 
105     @Test
106     public void testGetNextWords() {
107         String word = "chen";
108         Set<String> dict = new HashSet<>();
109         dict.add("chea");
110         dict.add("cheb");
111         dict.add("chec");
112         dict.add("chan");
113         dict.add("chbn");
114         dict.add("chba");
115         dict.add("chca");
116         dict.add("cdca");
117 
118 //        ArrayList<String> nextWords = getNextWords(word, dict);
119 //        System.out.println(Arrays.toString(nextWords.toArray()));
120         System.out.println(ladderLength(word,"cdca",dict));
121     }
122 
123 }