LeetCode 127. 单词接龙（BFS最短路）_单词数最少的接龙

题目描述
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：

• 序列中第一个单词是 beginWord 。
• 序列中最后一个单词是 endWord 。
• 每次转换只能改变一个字母。
• 转换过程中的中间单词必须是字典 wordList 中的单词。

给你两个单词 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

• 由于BFS在边权重为1的情况下具有最短路这一性质，因为扩展的时候想扩展边长度为1的点，然后扩展边长度为2的点，
• DFS不具有最短路的性质，因为每次扩展的时候是按照树的深度扩展，扩展完一个分支才去扩展另一个分支，DFS题目中会涉及到回溯和剪枝。

因此本题目使用BFS，在构造图时，首先枚举单词的每个字母，替换某个字母之后如果在字典中出现过，且没被遍历过就加入路径，路径长度就加1，使用 dist[t] 表示起点到 t 的最短路径，如果遍历到该点路径就加1。如果该点恰好是终点，那么返回dist，否则将该点加入到队列中。

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_map<string,int> dist;
        unordered_set<string> s;
        dist[beginWord]=1;
        for(auto x:wordList) s.insert(x);
        queue<string> q;
        q.push(beginWord);
        while(q.size())
        {
            auto t=q.front();
            q.pop();
            string r=t;
            for(int i=0;i<t.size();i++)
            {
                t = r;//很关键，下一次循环的时候t已经不是之前原本的t了,已经被修改过，因此需要重新赋值
                for(char j='a';j<='z';j++)
                {
                    t[i]=j;
                    if(s.count(t) && dist.count(t)==0) 
                    {
                        dist[t]=dist[r]+1;
                        if(t==endWord) return dist[t];
                        q.push(t);
                    }
                }
            }
        }
        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