LeetCode127—Word Ladder

女爷i 2022-08-22 00:28 145阅读 0赞

# LeetCode127—Word Ladder #

## 原题 ##

> 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 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.

--------------------

## 分析1 ##

要把这题转化成图论的问题，下述思路构建图：

> **1.beginWord、endWord、wordList里面的词作为图中的节点。**  
> **2.以确定这些节点是否可达：如果变换一个字符能够到另一个单词则说明可达**  
> **3.对图进行广度优先搜索，找出起点到终点的长度。**

### **问题** ###

这是我最开始的思路，并且实现了，但是遇到了一个问题，就是 当wordList中单词太多则图的规模就会变得很大，**最终就会超时（Time Limit Exceeded）**,这里也贴出超时代码吧：

class Solution {
    private:
        bool isConnect(const string &a, const string&b)
        {
       //判断两个单词是否可达关系
            int count = 0;
            for (int i = 0; i < a.size(); i++)
            {
                if (a[i] != b[i])
                    count++;
                if (count > 1)
                    return false; 
            }
            if (count == 1)//只有一个字符不同
                return true;
            else
                return false;
        }
        void buildMap(vector<vector<int>>&wordMap, map<string,int>wordTable)
        {
            int mapSize = wordTable.size();
            for (auto it1 = wordTable.begin(); it1 != wordTable.end(); it1++)
            {
                for (auto it2 = it1; it2 != wordTable.end(); it2++)
                {
                    if (isConnect(it1->first, it2->first))
                    {
                    //初始化邻接矩阵（1-可达 0-不可达）
                        wordMap[it1->second][it2->second] = 1;
                        wordMap[it2->second][it1->second] = 1;
                    }
                }
            }
        }
        int BFS(vector<vector<int>>&wordMap, string start, string end, map<string, int>wordTable)
        {
            vector<bool>visit(wordTable.size(), false);//访问表
            queue<int>q;
            queue<int>d;//记录距离distance的辅助队列
            q.push(wordTable[start]);
            d.push(1);
            visit[wordTable[start]] = true;
            while (!q.empty())
            {
                int t = d.front();
                int i = q.front();
                d.pop();
                q.pop();
                if (i == wordTable[end])//找到终点
                {
                    return t;
                }
                for (int j = 0; j < wordMap.size(); j++)
                {
                    if (!visit[j] && wordMap[i][j] == 1)
                    {
                        visit[j] = true;
                        q.push(j);
                        d.push(t + 1);
                    }
                }
            }//end while
            return 0;
        }
    public:
        int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
            map<string, int>wordTable;//单词索引表
            wordTable[beginWord] = 0;
            wordTable[endWord] = 1;
            auto it = wordList.begin();
            int index = 2;
            for (; it != wordList.end(); it++)//
            {
                if (wordTable.find(*it)==wordTable.end())
                    wordTable[*it] = index++;//建立一个单词-索引表方便建图
            }
            int size = wordTable.size();
            vector<vector<int>> wordMap(size,vector<int>(size,0));//初始化邻接矩阵
            buildMap(wordMap, wordTable);//建图
            return BFS(wordMap, beginWord, endWord, wordTable);
            //return 0;
        }
    };

--------------------

## 分析2 ##

其实不用把整个图建出来，可以走一步看一步，也就是说：

> **当访问到节点A时，可以先求出所有跟节点A临接且未被访问的节点入队，然后按照BFS的思路做即可。**

但是，修改后的代码依然是超时，后来找原因发现是我在**“判断两个节点是否临接”**这个步骤中使用的算法效率太低，对比网上的思路：

> 我的方法是：把当前节点的单词current和wordList里面的所有词比较，不相同的字符的个数为1的时候return true，否则return false。这样做的缺点是，**不论如何都要遍历完整个wordList，查找时间复杂度是O(n)。**
> 
> 网上一种思路是：替换当前节点的单词current每个字符（从a~z），然后看看替换过后的单词是否在单词表中，这里我不理解的是，由于我们是用unordered\_set来保存单词表，**虽然最坏情况下的时间复杂度会到O(n)，但一般情况下是可以在常数时间O(1)下访问的，因此使用unordered\_set::find的时间复杂度是要低于线性时间复杂度的**，这样就提高了效率。

--------------------

### **代码** ###

class Solution {
    private:
        void buildMap(string end,vector<string>&connect,unordered_set<string>&visit,string& current,const unordered_set<string>&wordList)
        {
            connect.clear();
            string cur = current;
            /*
            超时：时间复杂度O(n)
            for(auto i=wordList.begin();i!=wordList.end();i++)
            {
                if(visit.find(*i)!=visit.end())
                    continue;
                if(isConnect(cur,*i))
                    connect.push_back(*i);
            }
            */
    
            #if 1
            for (int i = 0; i < cur.size(); i++)
            {
                char t = cur[i];
                for (char c = 'a'; c < 'z'; c++)
                {
                    if (c == t)
                    {
                        continue;
                    }
                    cur[i] = c;
                    if ((cur == end || wordList.find(cur) != wordList.end()) && (visit.find(cur) == visit.end()))
                    {
                        connect.push_back(cur);
                    }
                }
                cur[i]=t;
            }
            #endif
        }
        int BFS(string beginWord, string endWord, unordered_set<string>& wordList)
        {
            queue<string>q;
            queue<int>d;//路径distance的辅助队列
            unordered_set<string>visit;
            vector<string>connect;
            q.push(beginWord);
            d.push(1);
            while (!q.empty())
            {
                string current = q.front();
                int tmpDist = d.front();
                q.pop();
                d.pop();
                buildMap(endWord,connect, visit, current, wordList);//获取临接单词
                if (current == endWord)//找到终点
                {
                    return tmpDist;
                }
                for (int i = 0; i < connect.size(); i++)
                {
                    if (visit.find(connect[i]) == visit.end())//未被访问
                    {
                        visit.insert(connect[i]);
                        q.push(connect[i]);
                        d.push(tmpDist + 1);
                    }
                }
            }
            return 0;//没有找到路径
        }
    
    public:
        int ladderLength(string beginWord, string endWord, unordered_set<string>& wordList) {
            int res= BFS(beginWord, endWord, wordList);
            return res;
        }
    };

--------------------

## 参考 ##

unordered\_set::find时间复杂度  
[http://www.cplusplus.com/reference/unordered\_set/unordered\_set/find/][http_www.cplusplus.com_reference_unordered_set_unordered_set_find]

Complexity  
Average case: constant.  
Worst case: linear in container size.

[http_www.cplusplus.com_reference_unordered_set_unordered_set_find]: http://www.cplusplus.com/reference/unordered_set/unordered_set/find/