[C++]Leetcode127.单词接龙_c++给定一个词典,然后从中选择两个单词,一个是起点单词,一个是终点单词,计算从起

127.单词接龙

题目：给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

   每次转换只能改变一个字母。

   转换过程中的中间单词必须是字典中的单词。
1
2
3

说明:

   如果不存在这样的转换序列，返回 0。

   所有单词具有相同的长度。

   所有单词只由小写字母组成。

   字典中不存在重复的单词。

   你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
1
2
3
4
5
6
7
8
9

示例 1:

输入:

beginWord = “hit”,

endWord = “cog”,

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

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        //将单词的列表转换成哈希set（无序集合容器）
        unordered_set<string> dict(wordList.begin(), wordList.end());
        //如果当前dict容器中没有endword，则直接返回
        if(!dict.count(endWord)) return 0;

        //新建一个队列q用于此题的BFS
        queue<string> q;
        //定义一个哈希表words，key为单词，value为单词修改了的字母的位数
        unordered_map<string, int> words;
        //beginword初始化为-1
        words[beginWord] = -1;
        //将beginword入队
        q.push(beginWord);
        int l = beginWord.length();
        //用于统计最短长度

        int step = 0;
        while(!q.empty())
        {
            //q不为空时，step进行累加
            step++;
            //for循环遍历q的大小
            for(int size = q.size(); size > 0; size--)
            {
                //取出q的首元素并删除
                string w = q.front();
                q.pop();
                //用loc记录当前单词w修改了的某一位字母的位数
                int loc = words[w];
                //遍历beginword的长度，从单词的第一个字母开始对每一个字母从a-z进行替换
                for(int i = 0; i < l; i++)
                {
                    //当前位字母替换过了，不再进行重复操作
                    if(loc == l) continue;
                    char ch = w[i];
                    for(int j = 'a'; j <= 'z'; j++)
                    {
                        //替换
                        w[i] = j;
                        //若当前单词与endword相同，则找到了答案，返回step+1
                        if(w == endWord) return step+1;
                        //若当前单词不在字典中，则中断此次循环
                        if(!dict.count(w)) continue;
                        //更新words
                        words[w] = i;
                        //字典里的单词只能使用一次，使用完之后删除
                        dict.erase(w);
                        //将当前新单词入队，接着进行下一轮循环
                        q.push(w);
                    }
                    //将替换过的单词复位，以便进行下一位字母的替换
                    w[i] = ch;
                }
            }
        }
        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
49
50
51
52
53
54
55
56
57
58
59
60
61
62

视频讲解：

https://www.bilibili.com/video/BV1yt411Y7Me?t=888

[[C++]Leetcode超高效刷题顺序及题目详解笔记（持续更新中）]