个人主页：C++忠实粉丝
欢迎 点赞???? 收藏✨ 留言✉ 加关注????本文由 C++忠实粉丝 原创

BFS解决最短路问题(3)_单词接龙

收录于专栏【经典算法练习】
本专栏旨在分享学习算法的一点学习笔记，欢迎大家在评论区交流讨论????   

目录

1, 题目链接

2. 题目描述

3. 解法

算法思路 :

代码展示:

4. 算法总结

---

1, 题目链接

OJ链接 : 单词接龙https://leetcode.cn/problems/word-ladder/description/

2. 题目描述

字典 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 中的所有字符串 互不相同

3. 解法

算法思路 :

这道题和上到题简直一模一样, 算法思路也是, 所以大家可以先去看前面的一道题:

BFS解决最短路问题(2)_最小基因变化-****博客

数据结构：

使用 unordered_set 作为访问集合（vis），记录已经访问过的单词，避免重复访问。
使用另一个 unordered_set 作为单词库（hash），快速查找单词列表中的单词。

初始检查：

如果 endWord 不在单词列表中，返回 0（无法到达目标）。
如果 beginWord 和 endWord 相同，直接返回 0（不需要转换）。

BFS过程：

将 beginWord 入队，并标记为已访问。
进入主循环，直到队列为空：
每次处理当前层的单词，记录当前层的大小（sz）。
对于队列中的每个单词：
尝试在每个位置替换为 a 到 z 之间的每个字符，生成新的单词。
检查新生成的单词是否在单词列表中且未被访问：
如果新单词是 endWord，返回当前的步数（ret）。
否则，将新单词入队并标记为已访问。
每完成一层的处理，增加步数计数（ret）。

返回结果：

如果队列处理完仍未找到目标单词，返回 0。

代码展示:

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) 
    {
        unordered_set<string> vis;
        unordered_set<string> hash(wordList.begin(), wordList.end());

        if(!hash.count(endWord)) return 0;
        if(beginWord == endWord) return 0;

        queue<string> q;
        q.push(beginWord);
        vis.insert(beginWord);

        int ret = 1;
        while(q.size())
        {
            ret++;
            int sz = q.size();
            for(int k = 0; k < sz; k++)
            {
                string t = q.front();
                q.pop();
                for(int i = 0; i < t.size(); i++)
                {
                    string tmp = t;
                    for(char ch = 'a'; ch <= 'z'; ch++)
                    {
                        tmp[i] = ch;
                        if(hash.count(tmp) && !vis.count(tmp))
                        {
                            if(tmp == endWord) return ret;
                            q.push(tmp);
                            vis.insert(tmp);
                        }
                    }
                }
            }
        }  
        return 0;  
    }
};

 

4. 算法总结

时间复杂度
最坏情况下，时间复杂度为 O(M* N * 26)，其中 M 是单词的长度，N 是单词列表的大小。每个单词在每个字符的位置都尝试替换 26 个字母。
总结
该算法通过 BFS 寻找单词转换的最短路径，确保每一步的生成单词是合法的，并且有效管理访问状态。BFS 的特性确保找到的第一条到达目标单词的路径就是最短路径，从而高效地解决了问题。