剑指 Offer II 108. 单词演变

image.png

思路： image.png 每次都找下一层符合规则的单词。

  1.     public int ladderLength(String beginWord, String endWord, List<String> wordList) {
  2.         Deque<String> queue = new LinkedList<>();
  3.         queue.offer(beginWord);
  4.         int count = 1;
  5.         //存储已经遍历过的词
  6.         List<String> dumplicate = new ArrayList<>();
  7.         while (!queue.isEmpty()) {
  8.             int size = queue.size();
  9.             for (int i = 0; i < size; i++) {
  10.                 String word = queue.poll();
  11.                 //存储遍历了几层，找到几层说明有几个词。
  12.                 count++;
  13.                 List<String> nexts = getNext(word, wordList);
  14.                 if (nexts.size() == 0) {
  15.                     return -1;
  16.                 }
  17.                 for (String next : nexts) {
  18.                     if (dumplicate.contains(next)) {
  19.                         continue;
  20.                     }
  21.                     if (next.equals(endWord)) {
  22.                         return count;
  23.                     }
  24.                     dumplicate.add(next);
  26.                     queue.offer(next);
  27.                 }
  28.             }
  30.         }
  31.         return -1;
  32.     }
  34.     private List<String> getNext(String word, List<String> wordList) {
  35.         List<String> list = new ArrayList<>();
  36.         for (char i = 'a'; i < 'z'; i++) {
  37.             for (int j = 0; j < word.length(); j++) {
  38.                 String pNext = changeWord(word, i, j);
  39.                 if (wordList.contains(pNext)) {
  40.                     list.add(pNext);
  41.                 }
  42.             }
  43.         }
  44.         return list;
  45.     }
  47.     private String changeWord(String word, char i, int j) {
  48.         char[] words = word.toCharArray();
  49.         words[j] = i;
  50.         return new String(words);
  51.     }