【BFS最短路问题】单词接龙

利刃大大

发布于 2025-03-05 08:17:32

5400

代码可运行

文章被收录于专栏：csdn文章搬运csdn文章搬运

运行总次数：0

代码可运行

127. 单词接龙

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> ... -> sk：

每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

示例 1：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

提示：

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有字符串 互不相同

解题思路：边权为一的最短路问题 `->` bfs解决

这道题其实和 433. 最小基因变化 是类似的，只不过细节上有些不同罢了，因为思想是类似的，所以为什么可以转化为边权为一的最短路问题，这里就不再赘述了，具体可以参考上一道题的笔记！

我们主要来讲一下这道题的不同之处：这道题没有明确指出转化字符有哪些，而上一道是直接给出一个转化字符序列的。

这就导致了会出现这种时间复杂度比较高的思路，也是我一开始想到的思路：遍历 wordList 中所有字符串，如果 wordList[i] 没出现过，并且和 front 相差一个字符，才进行处理。虽然看起来没问题，但是每次去判断是否和 front 相差一个字符，我们要单独写一个带有循环的函数，又放在了遍历 wordList 中所有字符串的循环中，此时相当于就一个节点判断的时间复杂度来说，就达到了 O(n^2)，虽然在这道题是跑的过去的，但是时间复杂度是不容乐观的：

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> used;										   // 存储已经枚举过的单词，方便去重
        unordered_set<string> word_hash(wordList.begin(), wordList.end()); // 存储wordList中的单词，便于快速索引
        
        // 先进行边界处理
        if(word_hash.count(endWord) == 0)
            return 0;

        queue<string> bfs;
        bfs.push(beginWord);
        int step = 1;
        while(!bfs.empty())
        {
            step++; // 进入一层广度就让step累加

            int size = bfs.size();
            while(size--)
            {
                string front = bfs.front();
                bfs.pop();
                
                // 遍历wordList中所有字符串
                for(int i = 0; i < wordList.size(); ++i)
                {
                    // 如果wordList[i]没出现过，并且和front相差一个字符，才进行处理
                    // 时间复杂度高的原因是one_char()函数也是一个循环
                    if(used.count(wordList[i]) == 0 && one_char(front, wordList[i]) == true)
                    {
                        // 如果就是结果字符串，则直接返回
                        if(endWord == wordList[i])
                            return step;
                        
                        // 不是的话则加入队列中作为中间序列
                        bfs.push(wordList[i]);
                        used.insert(wordList[i]);
                    }
                }
            }
        }
        return 0;
    }
	
    // 判断两个字符串是否相差一个字符
    bool one_char(string& s1, string& s2)
    {
        int count = 0;
        for(int i = 0; i < s1.size(); ++i)
        {
            if(s1[i] != s2[i])
            {
                if(count == 0)
                    count++;
                else
                    return false;
            }
        }
        return count == 0 ? false : true;
    }
};

所以后面改变了一下思路，仔细一想是没有利用上 word_hash 这个哈希表来快速索引，又因为题目说 beginWord、endWord 和 wordList[i] 由小写英文字母组成，那么我们可以像 433. 最小基因变化 这道题一样，修改字符串上的字符，然后根据 word_hash 来快速判断是否存在修改后的字符串，这样子效率是非常高的。而 修改的字符，就在小写字母 a~z 范围内，这个并不难理解！

所以修改完的代码如下所示，只需要看循环那部分代码即可：

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> used;										   // 存储已经枚举过的单词，方便去重
        unordered_set<string> word_hash(wordList.begin(), wordList.end()); // 存储wordList中的单词，便于快速索引
        
        // 先进行边界处理
        if(word_hash.count(endWord) == 0)
            return 0;

        queue<string> bfs;
        bfs.push(beginWord);
        int step = 1;
        while(!bfs.empty())
        {
            step++; // 进入一层广度就让step累加

            int size = bfs.size();
            while(size--)
            {
                string front = bfs.front();
                bfs.pop();
                
                // 不是遍历wordList，而是遍历字符串front的长度，进行字符的修改
                for(int i = 0; i < front.size(); ++i)
                {
                    string tmp = front; // 细节：因为不能修改front，所以用临时变量tmp
                    for(char c = 'a'; c <= 'z'; ++c)
                    {
                        tmp[i] = c; // 修改字符串中的字符
                        
                        // 使用两个哈希表进行快速索引判断，思路和上面是一样的！
                        if(used.count(tmp) == 0 && word_hash.count(tmp) != 0)
                        {
                            // 如果就是结果字符串，则直接返回
                            if(endWord == tmp)
                                return step;
                            
                            // 不是的话则加入队列中作为中间序列
                            bfs.push(tmp);
                            used.insert(tmp);
                        }
                    }
                }
            }
        }
        return 0;
    }
};

可以看到两个代码跑出来的时间复杂度级别是天差地别的，超过了十倍！