Word Ladder

谁践踏了优雅 2022-05-21 07:18 178阅读 0赞

# LeetCode\[127. Word Ladder\] 题解 难度\[medium\] #

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

Only one letter can be changed at a time  
Each intermediate word must exist in the word list  
For example,

Given:  
beginWord = “hit”  
endWord = “cog”  
wordList = \[“hot”,”dot”,”dog”,”lot”,”log”\]

As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,  
return its length 5.

Note:

Return 0 if there is no such transformation sequence.  
All words have the same length.  
All words contain only lowercase alphabetic characters.  
大概意思就是给定两个长度相同的单词，找到一个方法，让第一个单词变化到第二个单词，每次只能变化一个字母，而且中间出现的都必须是字典里的单词，求这个转换次数最少的方法要用经过多少个单词。

**思路分析：**  
最开始看到这个题的时候，可能会不知道怎么做，不过稍微想想，就可以想到，可以把最开始的单词的所有相差一个字母的单词都找出来，一个个尝试，再一个个试下去，总会找到的。再认真想想，咦？这不就是搜索吗，是不是想到了什么。可以看出来，这题其实是一道关于图的题，问题就是一个无权图求最短路径的问题，我们都知道有权图求最短路径要用dijistra算法，无权图更简单，只要用BFS就可以了。所以可以分析出来，这个题目的解法是BFS。  
但是确定了使用BFS以后，还有一些问题没有解决，因为题目并没有给定图，我们还得自己构建一个图，怎么构建呢？在字典中把长度相同的单词都遍历一遍，构建一个二维数组，也就是邻接表，这样就可以做了。这个想法是正确的，但会超时，因为效率太低，由于要把所有长度单词遍历一遍，并且比较和哪些单词相差一个单词，需要用一个二重循环实现，所以复杂度是O(n2)，字典里单词数量大， 这个复杂度的算法就会很低效。  
因为BFS已经确定下来了，想要降低复杂度应该是从构建图这里入手，构建邻接表显然没那么必要，因为那么多的单词里面，只有少数单词之间是可以一步转换的，如果不能一个个遍历来找，我们还可以自己创造，通过改变当前单词，来确定这个单词的邻居，通过把单词的每个字母都从‘a’到‘z’变化（除了原本自身），来产生新单词，这样的单词一定是一步可达的，再判断这新单词是否存在于字典中，若存在，则放进队列中（BFS算法进行），这里注意还要把新产生的单词从词典中删除，避免出现死循环，例如hot变成dot以后，dot又变回了hot，这样一来，时间复杂度是O(26\*单词长度\*n），比之前要高效，代码实现如下，可通过

class Solution {
    public:
        int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {    
            if(beginWord.size()==0||endWord.size()==0)  return 0;
            if(beginWord.size()!=endWord.size())    return 0; 
    
            int n = beginWord.size();
            bool exist = false;
            int step = 1; 
            queue<string> q;  //BFS的队列
    
            while(!q.empty())   q.pop();
            q.push(beginWord);
            q.push("1"); //用于分割各层 
            wordList.erase(beginWord);  //防止下一层的单词变化产生之前已经出现的单词，入栈后就把单词删掉 
            while(!q.empty()){
                string word = q.front();
                q.pop(); 
                if(word == endWord){
                    exist = true;
                    break;
                }
                if(word == "1"){
                    step++;
                    continue;
                }
                for(int i=0; i<n; ++i){
                    char temp = word[i];
                    for(char x='a'; x<='z'; x++){
                        string tmp = word;
                        if(x!=temp){
                            tmp[i] = x;
                            if(wordList.find(tmp) != wordList.end())    q.push(tmp);
                            wordList.erase(tmp);
                        }
                    }
                }
                if(!q.empty()&&q.front()=="1")  //若对首为分割标记1，说明这一层已经遍历完成，可以新加入一个分层标记 
                q.push("1"); 
            }  
            if(exist)   return step;
            else    return 0; 
        }
    };
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15 
       16 
       17 
       18 
       19 
       20 
       21 
       22 
       23 
       24 
       25 
       26 
       27 
       28 
       29 
       30 
       31 
       32 
       33 
       34 
       35 
       36 
       37 
       38 
       39 
       40 
       41 
       42 
       43 
       44

提交以后可以看到  
![这里写图片描述][20160906150736343]  
运行时间耗费496ms，只打败了17%的人，说明这个算法效率还是比较低的，仍可以改进。

由于这个题目，我们的起点的目标点都是确定的，所以可以使用双向BFS方法提高效率，由于BFS每下一层搜索范围就大了很多，如果双向开始，可以大大减小搜索范围，提高效率，实现代码如下

class Solution {
    public:
        int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
            if(beginWord.size()==0||endWord.size()==0)  return 0;
            if(beginWord.size()!=endWord.size())    return 0; 
    
            unordered_set<string> head,tail,*phead,*ptail;  
            head.insert(beginWord);
            tail.insert(endWord);
            int step = 2;   //因为是双向，从一开始就有2层 
    
            while(!head.empty()&&!tail.empty()){
                //双向交替进行BFS，每次选择分支少的一边开始 
                if(head.size()<tail.size()){
                    phead = &head;
                    ptail = &tail;
                }
                else{
                    phead = &tail;
                    ptail = &head;
                }
                unordered_set<string> temp; 
                unordered_set<string>::iterator it;
                for(it=phead->begin(); it!=phead->end(); ++it){
                    string word = *it;
                    wordList.erase(word);
                    int n = word.size();
                    for(int i=0; i<n; ++i){
                        string tmp = word;
                        for(char x='a'; x<='z'; ++x){
                            if(x!=tmp[i]){
                                tmp[i] = x;
                                if(ptail->find(tmp)!=ptail->end())     
                                return step;
                                if(wordList.find(tmp)!=wordList.end()){
                                    temp.insert(tmp);
                                    wordList.erase(tmp);
                                }
                            }
                        }
                    }        
                }
                step++;
                swap(*phead,temp);  //更新phead 
            }
            return 0;
        }
    };
    
     
      
       1 
       2 
       3 
       4 
       5 
       6 
       7 
       8 
       9 
       10 
       11 
       12 
       13 
       14 
       15 
       16 
       17 
       18 
       19 
       20 
       21 
       22 
       23 
       24 
       25 
       26 
       27 
       28 
       29 
       30 
       31 
       32 
       33 
       34 
       35 
       36 
       37 
       38 
       39 
       40 
       41 
       42 
       43 
       44 
       45 
       46 
       47 
       48

![这里写图片描述][70]  
只花费了69ms，打败了88%的人，显然这个方法要比原来的方法高效得多。

[20160906150736343]: /images/20220521/3b2355a71c4c4e03a166644ae21f7bbb.png
[70]: /images/20220521/dbc1da73222a4e5fa3f41e5682bfbf3b.png