本文共 2728 字，大约阅读时间需要 9 分钟。

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.

Each transformed word must exist in the word list. Note that beginWord is not a transformed word. Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:

Input:

beginWord = “hit”,

endWord = “cog”,

wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]

Output: 5

Explanation: As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,

return its length 5.

我的想法

刚拿到这道题的我没有什么想法，头脑一片空白

解答

jiuzhang solution:

隐式图，每次只能变一个字符，两个邻接单词之间肯定只有一个字符不一样。 虽然知道怎么做了，但是还是不知道为什么这道题可以想到用图来做

class Solution {
       public int ladderLength(String beginWord, String endWord, List
   
     wordList) {
           if(beginWord.equals(endWord)) {
               return 1;        }                //构造查询集合dict        Set
    
      dict = new HashSet<>();        for(String word : wordList) {
               dict.add(word);        }                //bfs        Set
     
       visited = new HashSet<>();        Queue
      
        queue = new LinkedList<>();        queue.offer(beginWord);        visited.add(beginWord);        int length = 1;        while(!queue.isEmpty()) {
               length++; //路径长度            int size = queue.size();            for(int i = 0; i < size; i++) {
                   String cur = queue.poll();                //获取邻接词                for(String word : getNext(dict, cur)) {
                       if(visited.contains(word)) {
                           continue;                    }                    if(endWord.equals(word)) {
                           return length;                    }                    queue.offer(word);                    visited.add(word);                }            }        }        return 0;    }    /*	getNext()有两种写法：	N:单词总数	L:单词长度	1. for(word 单词总数) O(N)	   		比较当前单词cur与dict中的单词word是否只相差一个字符 O(L)	2. for(单词长度) O(L)			for(25个小写字符) 25				生成新单词 O(L)				比较新单词是否在dict中 O(L)	第1种方式O(N*L); 第2种方式O(L*25*2L)=>O(50*L^2)	如果N >> L，则第二种方式更好，否则第一种更好	*/    private ArrayList
       
         getNext(Set
        
          dict, String cur) { ArrayList
         
           next = new ArrayList<>(); //对字符串cur的每一个字符都进行枚举替换 for(int i = 0; i < cur.length(); i++) { for(char c = 'a'; c <= 'z'; c++) { char[] chars = cur.toCharArray(); //跳过自身 if(c == chars[i]) { continue; } chars[i] = c; String str = new String(chars); //如果有，说明str与cur邻接 if(dict.contains(str)) { next.add(str); } } } return next; }}
         
        
       
      
     
    
   

转载地址：http://vkqvb.baihongyu.com/